zoj 3228 覆盖及非覆盖串的多次匹配

题目题意：

给定多个小串，在一个长串中寻找这些串的匹配次数，有些统计的是可覆盖的，有些统计的是非覆盖的

先可以简单理解一下，建立ac自动机后，当前节点包含的字符串必然被把它作为fail指针的节点包含，所以一开始写了个set[MAX],然后MLE了

如果一个当前串被完全访问了，那么这个串一定是在整个fail指针的最后面的，所以那个节点在访问中一直沿着fail指针往下走一定是能走到的，在记录一个

上一次访问的位置，就能判断当前位置是否重复覆盖了

然后根据初始记录的字符串对应的节点位置，输出在那个节点的访问次数就行了

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <queue>

 #include <set>

 using namespace std;

 #define clr(x) memset(x , 0 , sizeof(x))

 #define CHAR_SIZE 26

 #define MAX_SIZE 600010

 #define N 100005

 char str[MAX_SIZE];

 char s[];

 int n ,  cnt[MAX_SIZE][];

 int pos[N] , flag[N];

 struct AC_Machine{

     int sz , ch[MAX_SIZE][CHAR_SIZE] , fail[MAX_SIZE] , deep[MAX_SIZE] , val[MAX_SIZE] , pre[MAX_SIZE];

     void init(){

         sz = ;

         clr(ch[]) , clr(val);

         pre[] = ;

         cnt[][] = cnt[][] = ;

     }

     void insert(char *s , int p){

         int n = strlen(s) , u=;

         for(int i= ; i<n ; i++){

             int c = s[i]-'a';

             if(!ch[u][c]){

                 clr(ch[sz]);

                 cnt[sz][] = cnt[sz][] = pre[sz] = val[sz] = ;

                 ch[u][c] = sz++;

             }

             u = ch[u][c];

             deep[u] = i+;

         }

         val[u] = ;

         pos[p] = u;

     }

     void get_fail(){

         queue<int> Q;

         fail[] = ;

         for(int c= ; c<CHAR_SIZE ; c++){

             int u = ch[][c];

             if(u) {Q.push(u);fail[u]=;}

         }

         while(!Q.empty()){

             int r = Q.front();

             val[r] |= val[fail[r]];

             Q.pop();

             for(int c= ; c<CHAR_SIZE ; c++){

                 int u = ch[r][c];

                 if(!u){ch[r][c]=ch[fail[r]][c] ; continue;}

                 fail[u] = ch[fail[r]][c];

                 Q.push(u);

             }

         }

     }

 }ac;

 void solve()

 {

     int cur =  , n=strlen(str);

     for(int i= ; i<=n ; i++){

         int c = str[i-]-'a';

         cur = ac.ch[cur][c];

         int v = cur;

         while(v && ac.val[v]){

             cnt[v][]++;

           //  cout<<str[i-1]<<" "<<v<<endl;

             if(i-ac.pre[v]>=ac.deep[v]){

                 cnt[v][]++;

                 ac.pre[v] = i;

             }

             v = ac.fail[v];

         }

     }

 }

 int main()

 {

   //  freopen("in.txt" , "r" , stdin);

     int cas = ;

     while(~scanf("%s" , str))

     {

         printf("Case %d\n" , ++cas);

         scanf("%d" , &n);

         int op;

         ac.init();

         for(int i= ; i<=n ; i++){

             scanf("%d%s" , &op , s);

             flag[i] = op;

             ac.insert(s , i);

         }

         ac.get_fail();

         solve();

         for(int i= ; i<=n ; i++){

             printf("%d\n" , cnt[pos[i]][flag[i]]);

         }

         puts("");

     }

     return ;

 }

巴特西

zoj 3228 覆盖及非覆盖串的多次匹配

最新文章

热门文章