[关闭]
@Junlier 2018-08-19T22:34:56.000000Z 字数 2008 阅读 1904

AC自动机模板2

字符串算法——AC自动机

题目

洛谷题目传送门

code

  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstdio>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<iomanip>
  7. #include<algorithm>
  8. #include<ctime>
  9. #include<queue>
  10. #include<stack>
  11. #include<vector>
  12. #define rg register
  13. #define il inline
  14. #define lst long long
  15. #define ldb long double
  16. #define N 155
  17. #define M 10550
  18. using namespace std;
  19. const int Inf=1e9;
  20. int n,tot,cnt;
  21. struct STRING{
  22. char s[75];
  23. int sum,num;
  24. }S[N];
  25. struct EDGE{
  26. int to,nxt;
  27. }ljl[M];
  28. int hd[M];
  29. char T[1000050];
  30. int End[N],sum[M];
  31. int trie[M][26],fail[M];
  32. il int read()
  33. {
  34. rg int s=0,m=0;rg char ch=getchar();
  35. while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
  36. while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  37. return m?-s:s;
  38. }
  39. il void init()
  40. {
  41. tot=0,cnt=0;
  42. memset(hd,0,sizeof(hd));
  43. memset(sum,0,sizeof(sum));
  44. memset(fail,0,sizeof(fail));
  45. memset(trie,0,sizeof(trie));
  46. }
  47. il void AC_Insert(rg char s[],rg int num)
  48. {
  49. rg int now=0,L=strlen(s);
  50. for(rg int i=0;i<L;++i)
  51. {
  52. rg int kk=s[i]-'a';
  53. if(!trie[now][kk])trie[now][kk]=++tot;
  54. now=trie[now][kk];
  55. }
  56. End[num]=now;
  57. }
  58. il void AC_get_fail()
  59. {
  60. queue<int>Q;
  61. while(!Q.empty())Q.pop();
  62. for(rg int i=0;i<26;++i)
  63. if(trie[0][i])Q.push(trie[0][i]);
  64. while(!Q.empty())
  65. {
  66. rg int now=Q.front();Q.pop();
  67. for(rg int i=0;i<26;++i)
  68. if(trie[now][i])
  69. {
  70. fail[trie[now][i]]=trie[fail[now]][i];
  71. Q.push(trie[now][i]);
  72. }
  73. else trie[now][i]=trie[fail[now]][i];
  74. }
  75. }
  76. il void AC_Query()
  77. {
  78. rg int now=0,L=strlen(T);
  79. for(rg int i=0;i<L;++i)
  80. {
  81. rg int kk=T[i]-'a';
  82. now=trie[now][kk],sum[now]++;
  83. }
  84. }
  85. il void add(rg int p,rg int q){ljl[++cnt]=(EDGE){q,hd[p]},hd[p]=cnt;}
  86. il int cmp(rg const STRING &a,rg const STRING &b)
  87. {
  88. if(a.sum==b.sum)return a.num<b.num;
  89. return a.sum>b.sum;
  90. }
  91. void dfs(rg int now)
  92. {
  93. for(rg int i=hd[now];i;i=ljl[i].nxt)
  94. dfs(ljl[i].to),sum[now]+=sum[ljl[i].to];
  95. }
  96. il void AC_get_ans()
  97. {
  98. for(rg int i=1;i<=tot;++i)
  99. add(fail[i],i);
  100. dfs(0);
  101. for(rg int i=1;i<=n;++i)
  102. S[i].sum=sum[End[i]];
  103. sort(S+1,S+n+1,cmp);
  104. printf("%d\n",S[1].sum);
  105. for(rg int i=1;i<=n;++i)
  106. {
  107. if(S[i].sum!=S[1].sum)break;
  108. cout<<S[i].s<<endl;
  109. }
  110. }
  111. int main()
  112. {
  113. while((n=read())&&n)
  114. {
  115. init();
  116. for(rg int i=1;i<=n;++i)
  117. {
  118. scanf("%s",S[i].s);
  119. AC_Insert(S[i].s,S[i].num=i);
  120. }
  121. scanf("%s",T);
  122. AC_get_fail();
  123. AC_Query();
  124. AC_get_ans();
  125. }
  126. return 0;
  127. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注