http://blog.csdn.net/soberman/archive/2009/03/10/3978071.aspx

view plaincopy to clipboardprint?

1. /*

2. 程序說明：多模式串匹配的AC自動機(jī)算法

3. 此題通過hdu 2222

4. 自動機(jī)算法可以參考《柔性字符串匹配》里的相應(yīng)章節(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;  //自動機(jī)里字符集的大小

13. struct  TrieNode   

14. {   

15.     TrieNode* fail;   

16.     TrieNode* next[MAXK];   

17. bool danger;   //該節(jié)點(diǎn)是否為某模式串的終結(jié)點(diǎn)

18. int  cnt;    //以該節(jié)點(diǎn)為終結(jié)點(diǎn)的模式串個數(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. }