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

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理

posts - 33, comments - 33, trackbacks - 0

hdu 2222 多模式串匹配

AC自動機用于多模式串匹配

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) 評論(0) 編輯收藏引用所屬分類: 算法題解

只有注冊用戶登錄后才能發表評論。


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

網站導航: 博客園 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| 亚洲午夜激情| 亚洲激情小视频| 亚洲欧美在线免费观看| 日韩亚洲一区二区| 久久国内精品自在自线400部| 亚洲人线精品午夜| 欧美一站二站| 亚洲欧美激情诱惑| 欧美a级在线| 欧美一级一区| 欧美另类在线观看| 开心色5月久久精品| 国产精品拍天天在线| 欧美国产精品va在线观看| 国产精品jizz在线观看美国 | 亚洲国产精品成人| 国产乱人伦精品一区二区| 亚洲黄色有码视频| 精品91在线| 亚洲欧美日韩精品久久久久| 亚洲精品视频二区| 久久久久久香蕉网| 久久久www成人免费无遮挡大片 | 国产精品video| 亚洲国产一成人久久精品| 狠狠色综合网| 欧美在线999| 香蕉av777xxx色综合一区| 欧美日韩国产高清| 最近中文字幕mv在线一区二区三区四区| 国产夜色精品一区二区av| 中文在线资源观看网站视频免费不卡 | 亚洲人成毛片在线播放| 久久精品一区二区三区不卡| 性欧美videos另类喷潮| 欧美日韩国产免费| 亚洲精品久久久久久久久久久| 亚洲国内高清视频| 久久色在线播放| 久热国产精品视频| 激情综合网址| 久久综合伊人77777尤物| 老司机精品福利视频| 国产啪精品视频| 香蕉成人伊视频在线观看 | 狠狠色综合网| 久久久精品一区| 欧美成人黄色小视频| 在线观看日韩| 欧美激情一区三区| 亚洲人成免费| 亚洲一区视频在线观看视频| 欧美四级在线观看| 亚洲欧美成人一区二区三区| 亚洲欧美综合网| 国外视频精品毛片| 久久亚洲视频| 99re6热在线精品视频播放速度| 中文精品一区二区三区| 欧美午夜一区二区| 亚洲欧美久久久| 免费久久99精品国产| 99国产精品久久久| 国产精品久久久久久久第一福利| 亚洲男人第一网站| 乱中年女人伦av一区二区| 亚洲精品一区二区在线观看| 欧美日韩精品在线观看| 亚洲免费网站| 媚黑女一区二区| 亚洲一区二区视频在线观看| 国产亚洲二区| 免费成人性网站| 在线视频一区观看| 免费成人av在线| 亚洲一区二区三区三| 国模私拍视频一区| 欧美日本国产一区| 欧美一区二区黄| 亚洲伦理在线| 久久免费少妇高潮久久精品99| 1000精品久久久久久久久| 欧美日本三级| 久久亚洲精品视频| 亚洲综合社区| 亚洲全部视频| 久久婷婷人人澡人人喊人人爽| 夜夜夜精品看看| 亚洲第一色中文字幕| 国产精品久久久久一区二区| 蜜桃av综合| 久久久国产精品亚洲一区| 中日韩在线视频| 亚洲黄色尤物视频| 久久在线免费视频| 欧美一级在线视频| 中文在线一区| 日韩午夜一区| 亚洲国产欧美精品| 国内成人自拍视频| 国产精品专区第二| 欧美视频在线观看视频极品| 免费观看日韩av| 久久综合电影| 久久久www成人免费毛片麻豆| 亚洲图片在线观看| 夜色激情一区二区| 亚洲精品久久久久久久久| 欧美顶级少妇做爰| 欧美96在线丨欧| 欧美aaaaaaaa牛牛影院| 久久综合伊人77777| 久久精品人人做人人综合| 亚洲欧美日韩视频一区| 亚洲一区三区电影在线观看| 一区二区三区四区国产| 亚洲三级毛片| 99国产精品视频免费观看一公开| 亚洲欧洲美洲综合色网| 亚洲激情午夜| 亚洲美女中文字幕| 亚洲精品欧美日韩专区| 日韩一级精品视频在线观看| 亚洲人成在线播放| 亚洲精品美女在线观看| 亚洲精品黄网在线观看| 夜夜嗨av一区二区三区四区| 9久草视频在线视频精品| 日韩一区二区精品在线观看| 中日韩美女免费视频网址在线观看 | 一区二区三区国产| 中文无字幕一区二区三区| 亚洲一区影音先锋| 欧美影院成人| 老鸭窝毛片一区二区三区 | 欧美一区午夜精品| 久久免费视频这里只有精品| 老司机成人网| 亚洲精品九九| 亚洲欧美日韩精品一区二区| 久久成人这里只有精品| 噜噜噜在线观看免费视频日韩 | 亚洲欧美一区二区三区在线| 久久国产一二区| 欧美gay视频激情| 国产精品国产| 精品福利电影| 亚洲一二三区精品| 久久女同互慰一区二区三区| 欧美激情精品久久久久久| 亚洲免费播放| 欧美一区二区三区在线免费观看| 老司机免费视频久久| 欧美视频免费| 1769国产精品| 亚洲先锋成人| 久久视频这里只有精品| 日韩视频在线免费| 久久精品一区二区| 国产精品二区在线| 亚洲欧洲日夜超级视频| 欧美一区二区三区精品| 亚洲国产精品成人综合色在线婷婷 | 久久久精彩视频| 99视频一区| 欧美电影在线| 狠狠色综合色区| 亚洲欧美中日韩| 亚洲激情自拍| 美女爽到呻吟久久久久| 国产欧美日韩精品专区| 一区二区三区成人| 亚洲黄网站黄|