也是一道AC自動機解決多模式串匹配的問題，注意的是用一個visited記錄id的出現，以及病毒的數組需要排序，當病毒數超過3時可以結束匹配。
代碼如下：
1
#include <stdio.h>
2#include <queue>
3#include <vector>
4#include <algorithm>
5using namespace std;
6
7struct TrieNode
8
{
9
int flag;
10 int fail;
11 int id;
12 int next[128];
13 void init()
14
{
15 flag = 0;
16 id = 0;
17 fail = -1;
18 for (int i = 0; i < 128; ++i)
19 {
20 next[i] = 0;
21
}
22 }
23
};
24const int N = 100000;
25TrieNode trieTree[N];
26bool visited[550];
27int cnt = 0;
28int lenB;
29int lenW;
30
31void insert(const char* _str,int _id)
32{
33 int rt = 0;
34 while(*_str)
35 {
36 int t = *_str;
37 if (trieTree[rt].next[t] == 0)
38 {
39 trieTree[++cnt].init();
40 trieTree[rt].next[t] = cnt;
41 }
42 rt = trieTree[rt].next[t];
43 ++_str;
44 }
45 trieTree[rt].flag++;
46 trieTree[rt].id = _id;
47}
48
49void buildAC()
50{
51 queue<int> Que;
52 Que.push(0);
53 int now;
54 while(!Que.empty())
55 {
56 now = Que.front();
57 Que.pop();
58 for (int i = 0; i < 128; ++i)
59 {
60 if(trieTree[now].next[i])
61 {
62 int p = trieTree[now].fail;
63 int q = trieTree[now].next[i];
64 while(p != -1 && trieTree[p].next[i] == 0)
65 p = trieTree[p].fail;
66 if (p == -1)
67 {
68 trieTree[q].fail = 0;
69 }
70 else
71 {
72 trieTree[q].fail = trieTree[p].next[i];
73 }
74 Que.push(q);
75 }
76 }
77 }
78}
79
80char buf[20000];
81
82vector<int> Match(const char* _str)
83{
84 vector<int> ret;
85 int rt = 0;
86 int p;
87 while(*_str)
88 {
89 int t = *_str;
90 if (trieTree[rt].next[t])
91 {
92 rt = trieTree[rt].next[t];
93 }
94 else
95 {
96 p = trieTree[rt].fail;
97 while(p != -1 && trieTree[p].next[t] == 0)
98 p = trieTree[p].fail;
99 if (p == -1)
100 {
101 rt = 0;
102 }
103 else
104 {
105 rt = trieTree[p].next[t];
106 }
107 }
108 p = rt;
109 while(p != 0 && trieTree[p].flag)
110 {
111 if (trieTree[p].flag && !visited[trieTree[p].id])
112 {
113 visited[trieTree[p].id] = true;
114 ret.push_back(trieTree[p].id);
115 if (ret.size() == 3)
116 {
117 return ret;
118 }
119 }
120 p = trieTree[p].fail;
121 }
122 ++_str;
123 }
124
125 return ret;
126}
127
128void Test()
129{
130 cnt = 0;
131 trieTree[cnt].init();
132 for (int i = 1; i <= lenB; ++i)
133 {
134 scanf("%s",buf);
135 insert(buf,i);
136 }
137 buildAC();
138 scanf("%d",&lenW);
139 int total = 0;
140 for (int i = 0; i < lenW; ++i)
141 {
142 scanf("%s",buf);
143 memset(visited,0,sizeof(visited));
144 vector<int> ret = Match(buf);
145 if (ret.size())
146 {
147 ++total;
148 sort(ret.begin(),ret.end());
149 printf("web %d:",i+1);
150 for (int j = 0; j < ret.size(); ++j)
151 {
152 printf(" %d",ret[j]);
153 }
154 printf("\n");
155 }
156 }
157 printf("total: %d\n",total);
158}
159
160int main()
161{
162 //freopen("data.txt","r",stdin);
163 while(scanf("%d",&lenB) != EOF)
164 {
165 Test();
166 }
167 return 0;
168}
posted on 2012-03-29 18:18
bennycen 閱讀(1292)
評論(0) 編輯 收藏 引用 所屬分類:
算法題解