Searching the String
题意：两种查询，普通的就是ac自动机模板，另外一种要求没有发生覆盖。
处理方式是判断一下如果当前匹配到的位置(u)减去上一次匹配到的位置（ed[u]）大于该字符的深度（deep[u])，就加1。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define CLR(m,a) memset(m,a,sizeof(m)) 4 5 const int maxnode=5*1e5+10; 6 const int sigma=26; 7 8 struct AC{ 9 int ch[maxnode][sigma],f[maxnode],last[maxnode]; 10 int val[maxnode],deep[maxnode]; 11 int cnt[maxnode][2]; 12 int ed[maxnode]; 13 int sz; 14 15 void init(){ 16 CLR(ch[0],0); 17 sz=1; 18 CLR(ed,-1); 19 CLR(val,0); 20 CLR(cnt,0); 21 } 22 23 int idx(char c){return c-'a';} 24 25 int inser(char *s){ 26 int u=0,n=strlen(s); 27 for(int i=0;i<n;i++){ 28 int c=idx(s[i]); 29 if(!ch[u][c]){ 30 CLR(ch[sz],0); 31 deep[sz]=i+1; // 32 ch[u][c]=sz++; 33 } 34 u=ch[u][c]; 35 } 36 val[u]=1; 37 return u; 38 } 39 40 void getfail(){ 41 queue<int> q; 42 f[0]=0; 43 last[0]=0; 44 for(int c=0;c<sigma;c++){ 45 int u=ch[0][c]; 46 if(u){ 47 f[u]=0; 48 last[u]=0; 49 q.push(u); 50 } 51 } 52 while(!q.empty()){ 53 int r=q.front(); 54 q.pop(); 55 for(int c=0;c<sigma;c++){ 56 int u=ch[r][c]; 57 if(!u) continue; 58 q.push(u); 59 int v=f[r]; 60 while(v&&!ch[v][c]) v=f[v]; 61 f[u]=ch[v][c]; 62 last[u]=val[f[u]]?f[u]:last[f[u]]; 63 } 64 } 65 } 66 void print(int u,int i){ 67 if(val[u]){ 68 cnt[u][0]++; 69 if(i-ed[u]>=deep[u]){ 70 cnt[u][1]++; 71 ed[u]=i; 72 } 73 print(last[u],i); 74 } 75 } 76 void query(char *s){ 77 int u=0,n=strlen(s); 78 for(int i=0;i<n;i++){ 79 int c=idx(s[i]); 80 while(u&&!ch[u][c]) u=f[u]; 81 u=ch[u][c]; 82 if(val[u]) print(u,i); 83 else if(last[u]) print(last[u],i); 84 } 85 } 86 }; 87 const int maxn=1e5+10; 88 int pos[maxn],c[maxn]; 89 char s[maxn],p[10]; 90 AC ac; 91 int main(){ 92 int kase=0; 93 while(scanf("%s",s)!=EOF){ 94 ac.init(); 95 printf("Case %d\n",++kase); 96 int n; 97 scanf("%d",&n); 98 for(int i=0;i<n;i++){ 99 scanf("%d%s",&c[i],p); 100 pos[i]=ac.inser(p); 101 } 102 ac.getfail(); 103 ac.query(s); 104 for(int i=0;i<n;i++){ 105 printf("%d\n",ac.cnt[pos[i]][c[i]]); 106 } 107 puts(""); 108 } 109 return 0; 110 }