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

题目题意：

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

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

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

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

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

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <queue>
  5 #include <set>
  6 using namespace std;
  7 #define clr(x) memset(x , 0 , sizeof(x))
  8 #define CHAR_SIZE 26
  9 #define MAX_SIZE 600010
 10 #define N 100005
 11 char str[MAX_SIZE];
 12 char s[1005];
 13 int n ,  cnt[MAX_SIZE][2];
 14 int pos[N] , flag[N];
 15 struct AC_Machine{
 16     int sz , ch[MAX_SIZE][CHAR_SIZE] , fail[MAX_SIZE] , deep[MAX_SIZE] , val[MAX_SIZE] , pre[MAX_SIZE];
 17     void init(){
 18         sz = 1;
 19         clr(ch[0]) , clr(val);
 20         pre[0] = 0;
 21         cnt[0][0] = cnt[1][0] = 0;
 22     }
 23 
 24     void insert(char *s , int p){
 25         int n = strlen(s) , u=0;
 26         for(int i=0 ; i<n ; i++){
 27             int c = s[i]-'a';
 28             if(!ch[u][c]){
 29                 clr(ch[sz]);
 30                 cnt[sz][0] = cnt[sz][1] = pre[sz] = val[sz] = 0;
 31                 ch[u][c] = sz++;
 32             }
 33             u = ch[u][c];
 34             deep[u] = i+1;
 35         }
 36         val[u] = 1;
 37         pos[p] = u;
 38     }
 39 
 40     void get_fail(){
 41         queue<int> Q;
 42         fail[0] = 0;
 43         for(int c=0 ; c<CHAR_SIZE ; c++){
 44             int u = ch[0][c];
 45             if(u) {Q.push(u);fail[u]=0;}
 46         }
 47         while(!Q.empty()){
 48             int r = Q.front();
 49             val[r] |= val[fail[r]];
 50             Q.pop();
 51             for(int c=0 ; c<CHAR_SIZE ; c++){
 52                 int u = ch[r][c];
 53                 if(!u){ch[r][c]=ch[fail[r]][c] ; continue;}
 54                 fail[u] = ch[fail[r]][c];
 55                 Q.push(u);
 56             }
 57         }
 58     }
 59 }ac;
 60 
 61 void solve()
 62 {
 63     int cur = 0 , n=strlen(str);
 64     for(int i=1 ; i<=n ; i++){
 65         int c = str[i-1]-'a';
 66         cur = ac.ch[cur][c];
 67         int v = cur;
 68         while(v && ac.val[v]){
 69             cnt[v][0]++;
 70           //  cout<<str[i-1]<<" "<<v<<endl;
 71             if(i-ac.pre[v]>=ac.deep[v]){
 72                 cnt[v][1]++;
 73                 ac.pre[v] = i;
 74             }
 75             v = ac.fail[v];
 76         }
 77     }
 78 }
 79 
 80 int main()
 81 {
 82   //  freopen("in.txt" , "r" , stdin);
 83     int cas = 0;
 84     while(~scanf("%s" , str))
 85     {
 86         printf("Case %d
" , ++cas);
 87         scanf("%d" , &n);
 88         int op;
 89         ac.init();
 90         for(int i=1 ; i<=n ; i++){
 91             scanf("%d%s" , &op , s);
 92             flag[i] = op;
 93             ac.insert(s , i);
 94         }
 95         ac.get_fail();
 96         solve();
 97 
 98         for(int i=1 ; i<=n ; i++){
 99             printf("%d
" , cnt[pos[i]][flag[i]]);
100         }
101         puts("");
102     }
103     return 0;
104 }