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

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

Plus:

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