[关闭]
@zzzc18 2017-07-31T13:41:10.000000Z 字数 4556 阅读 459

AC自动机

字符串


找到一份很好的注释代码

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<queue>
  7. #include<algorithm>
  8. using namespace std;
  9. struct Tree//字典树
  10. {
  11. int fail;//失配指针
  12. int vis[26];//子节点的位置
  13. int end;//标记有几个单词以这个节点结尾
  14. }AC[1000000];//Trie树
  15. int cnt=0;//Trie的指针
  16. inline void Build(string s)
  17. {
  18. int l=s.length();
  19. int now=0;//字典树的当前指针
  20. for(int i=0;i<l;++i)//构造Trie树
  21. {
  22. if(AC[now].vis[s[i]-'a']==0)//Trie树没有这个子节点
  23. AC[now].vis[s[i]-'a']=++cnt;//构造出来
  24. now=AC[now].vis[s[i]-'a'];//向下构造
  25. }
  26. AC[now].end+=1;//标记单词结尾
  27. }
  28. void Get_fail()//构造fail指针
  29. {
  30. queue<int> Q;//队列
  31. for(int i=0;i<26;++i)//第二层的fail指针提前处理一下
  32. {
  33. if(AC[0].vis[i]!=0)
  34. {
  35. AC[AC[0].vis[i]].fail=0;//指向根节点
  36. Q.push(AC[0].vis[i]);//压入队列
  37. }
  38. }
  39. while(!Q.empty())//BFS求fail指针
  40. {
  41. int u=Q.front();
  42. Q.pop();
  43. for(int i=0;i<26;++i)//枚举所有子节点
  44. {
  45. if(AC[u].vis[i]!=0)//存在这个子节点
  46. {
  47. AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
  48. //子节点的fail指针指向当前节点的
  49. //fail指针所指向的节点的相同子节点
  50. Q.push(AC[u].vis[i]);//压入队列
  51. }
  52. else//不存在这个子节点
  53. AC[u].vis[i]=AC[AC[u].fail].vis[i];
  54. //当前节点的这个子节点指向当
  55. //前节点fail指针的这个子节点
  56. }
  57. }
  58. }
  59. int AC_Query(string s)//AC自动机匹配
  60. {
  61. int l=s.length();
  62. int now=0,ans=0;
  63. for(int i=0;i<l;++i)
  64. {
  65. now=AC[now].vis[s[i]-'a'];//向下一层
  66. for(int t=now;t&&AC[t].end!=-1;t=AC[t].fail)//循环求解
  67. {
  68. ans+=AC[t].end;
  69. AC[t].end=-1;
  70. }
  71. }
  72. return ans;
  73. }
  74. int main()
  75. {
  76. int n;
  77. string s;
  78. cin>>n;
  79. for(int i=1;i<=n;++i)
  80. {
  81. cin>>s;
  82. Build(s);
  83. }
  84. AC[0].fail=0;//结束标志
  85. Get_fail();//求出失配指针
  86. cin>>s;//文本串
  87. cout<<AC_Query(s)<<endl;
  88. return 0;
  89. }

Ok the code above is gg;

original:

  1. #include<queue>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #define MAXN 60000
  6. using namespace std;
  7. int n;
  8. char tmp[20][200];
  9. char S[100000000+1];
  10. struct Trie{
  11. bool val[MAXN];
  12. int size,fail[MAXN],last[MAXN],ch[MAXN][27],num[MAXN];
  13. queue<int> que;
  14. int Sigma_Size;
  15. int idx(char c){
  16. return c-'a';
  17. }
  18. void insert(char *s){
  19. int len=strlen(s);int now=0;int i;
  20. for(i=0;i<len;i++){
  21. int c=idx(s[i]);
  22. if(!ch[now][c])
  23. ch[now][c]=++size;
  24. now=ch[now][c];
  25. }
  26. val[now]=1;
  27. }
  28. void Getfail(){
  29. int i;
  30. for(i=0;i<Sigma_Size;i++){
  31. if(ch[0][i]!=0){
  32. que.push(ch[0][i]);
  33. last[ch[0][i]]=fail[ch[0][i]]=0;
  34. }
  35. }
  36. while(!que.empty()){
  37. int fro=que.front();que.pop();
  38. int c;
  39. for(c=0;c<Sigma_Size;c++){
  40. int u=ch[fro][c];
  41. if(!u) continue;
  42. que.push(u);
  43. int j=fail[fro];
  44. while(j && !ch[j][c]) j=fail[j];
  45. fail[u]=ch[j][c];
  46. last[u]=val[fail[u]] ? fail[u] : last[fail[u]];
  47. }
  48. }
  49. }
  50. void print(int j){
  51. if(val[j]) num[j]++;
  52. if(j) print(last[j]);
  53. }
  54. void Find(char *s){
  55. int u=0;
  56. int len=strlen(s);
  57. int i;
  58. int now=0;
  59. for(i=0;i<len;i++){
  60. int c=idx(s[i]);
  61. int j=now;
  62. while(j && !ch[j][c]) j=fail[j];
  63. now=ch[j][c];
  64. if(val[now]) print(now);
  65. else print(last[now]);
  66. }
  67. }
  68. int query(char *s){
  69. int i;
  70. int now=0;
  71. int len=strlen(s);
  72. for(i=0;i<len;i++){
  73. int c=idx(s[i]);
  74. now=ch[now][c];
  75. }
  76. printf("%s %d\n",s,num[now]);
  77. }
  78. void clear(){
  79. memset(ch,0,sizeof(ch));
  80. memset(val,0,sizeof(val));
  81. memset(last,0,sizeof(last));
  82. memset(num,0,sizeof(num));
  83. memset(fail,0,sizeof(fail));
  84. size=0;
  85. }
  86. Trie(){
  87. clear();
  88. }
  89. };
  90. Trie T;
  91. void INIT(){
  92. scanf("%d",&n);
  93. int i;
  94. for(i=1;i<=n;i++){
  95. scanf("%s",tmp[i]);
  96. T.insert(tmp[i]);
  97. }
  98. scanf("%s",S);
  99. T.Getfail();
  100. }
  101. void solve(){
  102. int i;
  103. T.Find(S);
  104. for(i=1;i<=n;i++){
  105. T.query(tmp[i]);
  106. }
  107. }
  108. int main(){
  109. freopen("ACautomata.in","r",stdin);
  110. freopen("ACautomata.out","w",stdout);
  111. T.Sigma_Size=26;
  112. INIT();
  113. solve();
  114. return 0;
  115. }

Plus:

  1. #include<queue>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #define MAXN 60000
  6. using namespace std;
  7. int n;
  8. char tmp[20][200];
  9. char S[100000000+1];
  10. struct Trie{
  11. bool val[MAXN];
  12. int size,fail[MAXN],last[MAXN],ch[MAXN][27],num[MAXN];
  13. queue<int> que;
  14. int Sigma_Size;
  15. int idx(char c){
  16. return c-'a';
  17. }
  18. void insert(char *s){
  19. int len=strlen(s);int now=0;int i;
  20. for(i=0;i<len;i++){
  21. int c=idx(s[i]);
  22. if(!ch[now][c])
  23. ch[now][c]=++size;
  24. now=ch[now][c];
  25. }
  26. val[now]=1;
  27. }
  28. void Getfail(){
  29. int i;
  30. for(i=0;i<Sigma_Size;i++){
  31. if(ch[0][i]!=0){
  32. que.push(ch[0][i]);
  33. last[ch[0][i]]=fail[ch[0][i]]=0;
  34. }
  35. }
  36. while(!que.empty()){
  37. int fro=que.front();que.pop();
  38. int c;
  39. for(c=0;c<Sigma_Size;c++){
  40. int u=ch[fro][c];
  41. if(!u){
  42. ch[fro][c]=ch[fail[fro]][c];
  43. continue;
  44. }
  45. que.push(u);
  46. int j=fail[fro];
  47. while(j && !ch[j][c]) j=fail[j];
  48. fail[u]=ch[j][c];
  49. last[u]=val[fail[u]] ? fail[u] : last[fail[u]];
  50. }
  51. }
  52. }
  53. void print(int j){
  54. if(val[j]) num[j]++;
  55. if(j) print(last[j]);
  56. }
  57. void Find(char *s){
  58. int u=0;
  59. int len=strlen(s);
  60. int i;
  61. int now=0;
  62. for(i=0;i<len;i++){
  63. int c=idx(s[i]);
  64. int j=now;
  65. now=ch[j][c];
  66. if(val[now]) print(now);
  67. else print(last[now]);
  68. }
  69. }
  70. int query(char *s){
  71. int i;
  72. int now=0;
  73. int len=strlen(s);
  74. for(i=0;i<len;i++){
  75. int c=idx(s[i]);
  76. now=ch[now][c];
  77. }
  78. printf("%s %d\n",s,num[now]);
  79. }
  80. void clear(){
  81. memset(ch,0,sizeof(ch));
  82. memset(val,0,sizeof(val));
  83. memset(last,0,sizeof(last));
  84. memset(num,0,sizeof(num));
  85. memset(fail,0,sizeof(fail));
  86. size=0;
  87. }
  88. Trie(){
  89. clear();
  90. }
  91. };
  92. Trie T;
  93. void INIT(){
  94. scanf("%d",&n);
  95. int i;
  96. for(i=1;i<=n;i++){
  97. scanf("%s",tmp[i]);
  98. T.insert(tmp[i]);
  99. }
  100. scanf("%s",S);
  101. T.Getfail();
  102. }
  103. void solve(){
  104. int i;
  105. T.Find(S);
  106. for(i=1;i<=n;i++){
  107. T.query(tmp[i]);
  108. }
  109. }
  110. int main(){
  111. freopen("ACautomata.in","r",stdin);
  112. freopen("ACautomata.out","w",stdout);
  113. T.Sigma_Size=26;
  114. INIT();
  115. solve();
  116. return 0;
  117. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注