http://blog.csdn.net/soberman/archive/2009/03/10/3978071.aspx
view plaincopy to clipboardprint?
1. /*
2. 程序說明：多模式串匹配的AC自動機算法
3. 此題通過hdu 2222
4. 自動機算法可以參考《柔性字符串匹配》里的相應章節(jié)，講的很清楚
5. */
6. #include <stdio.h>
7. #include <string.h>
8.
9.
10. const int MAXQ = 500000+10;
11. const int MAXN = 1000000+10;
12. const int MAXK = 26; //自動機里字符集的大小
13. struct TrieNode
14. {
15. TrieNode* fail;
16. TrieNode* next[MAXK];
17. bool danger; //該節(jié)點是否為某模式串的終結點
18. int cnt; //以該節(jié)點為終結點的模式串個數(shù)
19. TrieNode()
20. {
21. fail = NULL;
22. memset(next, NULL, sizeof(next));
23. danger = false;
24. cnt = 0;
25. }
26. }*que[MAXQ], *root;
27. //文本字符串
28. char msg[MAXN];
29. int N;
30. void TrieInsert(char *s)
31. {
32. int i = 0;
33. TrieNode *ptr = root;
34. while(s[i])
35. {
36. int idx = s[i]-'a';
37. if(ptr->next[idx] == NULL)
38. ptr->next[idx] = new TrieNode();
39. ptr = ptr->next[idx];
40. i++;
41. }
42. ptr->danger = true;
43. ptr->cnt++;
44. }
45.
46. void Init()
47. {
48. int i;
49. char s[100];
50. root = new TrieNode();
51. scanf("%d", &N);
52. for(i = 0; i < N; i++)
53. {
54. scanf("%s", s);
55. TrieInsert(s);
56. }
57. }
58.
59. void Build_AC_Automation()
60. {
61. int rear = 1, front = 0, i;
62. que[0] = root;
63. root->fail = NULL;
64. while(rear != front)
65. {
66. TrieNode *cur = que[front++];
67. for(i = 0; i < 26; i++)
68. if(cur->next[i] != NULL)
69. {
70. if(cur == root)
71. cur->next[i]->fail = root;
72. else
73. {
74. TrieNode *ptr = cur->fail;
75. while(ptr != NULL)
76. {
77. if(ptr->next[i] != NULL)
78. {
79. cur->next[i]->fail = ptr->next[i];
80. if(ptr->next[i]->danger == true)
81. cur->next[i]->danger = true;
82. break;
83. }
84. ptr = ptr->fail;
85. }
86. if(ptr == NULL) cur->next[i]->fail = root;
87. }
88. que[rear++] = cur->next[i];
89. }
90. }
91. }
92.
93. int AC_Search()
94. {
95. int i = 0, ans = 0;
96. TrieNode *ptr = root;
97. while(msg[i])
98. {
99. int idx = msg[i]-'a';
100. while(ptr->next[idx] == NULL && ptr != root) ptr = ptr->fail;
101. ptr = ptr->next[idx];
102. if(ptr == NULL) ptr = root;
103. TrieNode *tmp = ptr;
104. while(tmp != NULL && tmp->cnt != -1)
105. {
106. ans += tmp->cnt;
107. tmp->cnt = -1;
108. tmp = tmp->fail;
109. }
110. i++;
111. }
112. return ans;
113. }
114.
115. int main()
116. {
117. int T;
118. scanf("%d", &T);
119. while(T--)
120. {
121. Init();
122. Build_AC_Automation();
123. //文本
124. scanf("%s", msg);
125. printf("%d\n", AC_Search());
126. }
127. return 0;
128. }