青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

<cite id="polxg"></cite>

<abbr id="polxg"><fieldset id="polxg"></fieldset></abbr>

C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合

:: 管理

posts - 33, comments - 33, trackbacks - 0

hdu 2222 多模式串匹配

AC自動(dòng)機(jī)用于多模式串匹配

1

#include <stdio.h>
2

#include <string.h>
3

#include <queue>
4

using namespace std;
5

6

const int N = 500005;
7

8

struct Trie
9

{
10

int flag;
11

int fail;
12

int next[26];
13

14

void Init()
15

{
16

flag = 0;
17

fail = -1;
18

for(int i = 0; i < 26; ++i)
19

next[i] = 0;
20

}
21

};
22

23

Trie trieTrees[N];
24

int treeCnt;
25

char strs[1000005];
26

int n;
27

28

void Insert(char* _str)
29

{
30

int rt = 0;
31

while(*_str != 0)
32

{
33

int t = *_str - 'a';
34

if(trieTrees[rt].next[t] == 0)
35

{
36

trieTrees[++treeCnt].Init();
37

trieTrees[rt].next[t] = treeCnt;
38

}
39

rt = trieTrees[rt].next[t];
40

++_str;
41

}
42

trieTrees[rt].flag++;
43

}
44

45

46

void BFS()
47

{
48

queue<int> Queue;
49

int rt = 0;
50

int p,q;
51

Queue.push(0);
52

while(!Queue.empty())
53

{
54

int now = Queue.front();
55

Queue.pop();
56

for(int t = 0; t < 26; ++t)
57

{
58

if(trieTrees[now].next[t])
59

{
60

p = trieTrees[now].fail;
61

q = trieTrees[now].next[t];
62

while(p !=-1 && trieTrees[p].next[t] == NULL)
63

p = trieTrees[p].fail;
64

if(p == -1)
65

trieTrees[q].fail = 0;
66

else
67

trieTrees[q].fail = trieTrees[p].next[t];
68

Queue.push(q);
69

}
70

}
71

}
72

}
73

74

int Match(char *_str)
75

{
76

int ret = 0;
77

int rt = 0;
78

int t,p;
79

while(*_str)
80

{
81

t = *_str - 'a';
82

if(trieTrees[rt].next[t])
83

rt = trieTrees[rt].next[t];
84

else
85

{
86

p = trieTrees[rt].fail;
87

while(p != -1 && (!trieTrees[p].next[t]))
88

p = trieTrees[p].fail;
89

if(p == -1)
90

rt = 0;
91

else
92

rt = trieTrees[p].next[t];
93

}
94

p = rt;
95

while(p != 0&& trieTrees[p].flag)
96

{
97

if(trieTrees[p].flag)
98

{
99

ret += trieTrees[p].flag;
100

trieTrees[p].flag = 0;
101

}
102

p = trieTrees[p].fail;
103

}
104

++_str;
105

}
106

return ret;
107

}
108

109

void Test()
110

{
111

scanf("%d",&n);
112

treeCnt = 0;
113

trieTrees[0].Init();
114

for(int i = 0; i < n; ++i)
115

{
116

while(gets(strs),strcmp(strs,"") == 0 );
117

Insert(strs);
118

}
119

BFS();
120

gets(strs);
121

int ret = Match(strs);
122

printf("%d\n",ret);
123

}
124

125

int main()
126

{
127

//freopen("data.txt","r",stdin);
128

int testcase;
129

scanf("%d",&testcase);
130

for(int i = 0; i < testcase; ++i)
131

Test();
132

return 0;
133

}

posted on 2012-03-29 18:15 bennycen 閱讀(1289) 評(píng)論(0) 編輯收藏引用所屬分類: 算法題解

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。


相關(guān)文章: hdu 2087 hud 1686 hdu 2896 多模式串匹配2 hdu 2222 多模式串匹配水題兩道 zoj 3542 poj 3074 逆序數(shù)及其求法 Poj 3310 判環(huán)+度 Poj 3104 二分答案 Poj1111 水題

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

<ins id="pjuwb"></ins>

<blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

<noscript id="pjuwb"></noscript>

<sup id="pjuwb"><pre id="pjuwb"></pre></sup>

<dd id="pjuwb"></dd>

<abbr id="pjuwb"></abbr>

国产精品av免费在线观看| 亚洲欧美电影在线观看| 午夜精品区一区二区三| 亚洲国产高清一区二区三区| 欧美日韩一区二区免费视频| 久久久久久999| 一本一本久久| 亚洲高清中文字幕| 国产欧美一区二区三区在线老狼| 欧美精品一区二区高清在线观看| 久久激情五月丁香伊人| 亚洲永久在线观看| 99视频精品免费观看| 欧美激情2020午夜免费观看| 久久免费视频在线| 欧美一区二区女人| 亚洲欧美久久久久一区二区三区| 亚洲免费av电影| 亚洲国产成人av在线| 国产一区二区三区在线免费观看 | 亚洲欧美国产视频| 亚洲激情不卡| 亚洲激情国产| 亚洲欧洲一区二区天堂久久 | 久久在线91| 久久久久国产精品一区二区| 久久国产免费看| 久久er精品视频| 午夜精品久久久久久久久| 亚洲一区二区少妇| 亚洲一区中文字幕在线观看| 一区二区三区免费观看| 日韩一级大片| 亚洲美女电影在线| 亚洲精品乱码| 最新中文字幕一区二区三区| 亚洲国产精品视频| 亚洲韩国青草视频| 亚洲经典视频在线观看| 亚洲精品美女在线观看| 亚洲美女视频网| 99热在线精品观看| 亚洲视频在线播放| 亚洲一区二区三区视频| 亚洲欧美精品一区| 欧美亚洲在线观看| 久久久精品日韩| 免费成人激情视频| 亚洲片在线资源| 亚洲六月丁香色婷婷综合久久| 一级日韩一区在线观看| 午夜精品理论片| 久久精品网址| 欧美精品一区二区三区四区| 国产精品国产三级国产专区53 | 亚洲欧美在线免费| 欧美一区二区黄| 美国成人直播| 欧美视频中文一区二区三区在线观看 | 久久久噜噜噜久噜久久 | 亚洲国产精品电影在线观看| 最新中文字幕亚洲| 夜夜精品视频| 亚洲欧美日韩久久精品| 久久精品99| 亚洲第一主播视频| 亚洲图片欧洲图片av| 欧美一区二区三区在线视频| 另类亚洲自拍| 国产精品h在线观看| 黄色精品网站| 一区二区高清在线观看| 欧美在线视频一区二区三区| 欧美电影免费观看高清| 在线视频亚洲| 久热综合在线亚洲精品| 国产精品成人一区| 亚洲国产精品一区二区第一页 | 国产精品一二三| 亚洲高清免费| 欧美亚洲日本网站| 亚洲国产精品视频一区| 亚洲免费综合| 欧美精品一区三区在线观看| 国产一区二区在线观看免费播放| 亚洲精品久久久久久久久久久久 | 欧美成人伊人久久综合网| 国产精品久久久久久久久婷婷| 在线播放日韩专区| 亚洲伊人伊色伊影伊综合网| 免费观看在线综合| 亚洲性xxxx| 欧美精品一区二区三区一线天视频| 国产日韩欧美视频| 一区二区三区久久网| 久久免费偷拍视频| 亚洲天堂av电影| 欧美精品久久久久久久久老牛影院| 国产亚洲欧美中文| 亚洲中字黄色| 亚洲人成在线观看一区二区| 久久久久国产精品麻豆ai换脸| 国产精品―色哟哟| 在线亚洲一区二区| 欧美黄色小视频| 久久久久久日产精品| 国产嫩草一区二区三区在线观看| 99热免费精品在线观看| 欧美国产精品久久| 久久精品国产一区二区三区免费看| 欧美亚洲成人网| 夜夜嗨一区二区三区| 亚洲国产精品成人综合| 久久亚洲私人国产精品va| 国产日韩亚洲| 午夜亚洲激情| 国产精品99久久99久久久二8 | 欧美刺激性大交免费视频| 韩曰欧美视频免费观看| 久久电影一区| 亚洲欧美日韩国产成人| 国产精品成人一区二区三区吃奶| 亚洲作爱视频| 亚洲精品婷婷| 欧美日韩大片| 在线视频欧美一区| 亚洲美女免费精品视频在线观看| 欧美国产激情| 一本久久青青| 亚洲高清成人| 免费试看一区| 麻豆av一区二区三区| 亚洲国产婷婷香蕉久久久久久99 | 亚洲欧美日韩精品| 国产伦一区二区三区色一情| 欧美一区二区国产| 欧美一级在线视频| 国产亚洲激情在线| 久久嫩草精品久久久精品一 | 国产精品乱码妇女bbbb| 亚洲欧美日韩一区二区三区在线| 亚洲一区欧美激情| 国产欧美在线播放| 久久全球大尺度高清视频| 久久免费国产| 亚洲人午夜精品免费| 日韩视频免费观看高清完整版| 欧美日韩性视频在线| 亚洲字幕一区二区| 性欧美8khd高清极品| 国内自拍亚洲| 亚洲高清视频中文字幕| 欧美日韩999| 小处雏高清一区二区三区| 欧美在线精品免播放器视频| 在线精品国产欧美| 亚洲欧洲一区二区在线播放| 国产精品高清免费在线观看| 久久久久久亚洲综合影院红桃 | 亚洲国产综合在线| 欧美网站在线观看| 久久精品久久99精品久久| 久久久久久91香蕉国产| 日韩一级黄色片| 午夜一区二区三区不卡视频| 亚洲国产精品久久久久秋霞不卡| 99视频精品| 一区二区三区在线观看欧美| 亚洲美女毛片| 韩国女主播一区| 亚洲人体影院| 国产视频欧美视频| 欧美激情一区二区三区高清视频 | 欧美视频中文字幕在线| 久久久国产精品亚洲一区 | 国产亚洲福利一区| 亚洲国产精品999| 国产精品乱码妇女bbbb| 欧美成人激情在线| 国产精品一二三视频| 欧美激情精品久久久久久| 国产精品欧美精品| 欧美激情在线| 国产欧美日韩在线观看| 欧美激情精品久久久久久久变态| 欧美网站在线| 欧美激情在线有限公司| 国产欧美日韩亚洲| 亚洲国产日日夜夜| 国内外成人免费视频| 日韩视频在线观看| 韩国欧美一区| 亚洲制服av| 一区二区不卡在线视频午夜欧美不卡在 | 亚洲欧美日韩一区二区在线| 亚洲最黄网站| 你懂的国产精品永久在线| 久久精品国产久精国产思思| 欧美日韩综合视频网址| 亚洲承认在线|

<cite id="ykgzl"></cite>