题意
给出n个模式串和一个文本串，输出各个模式串在文本串中出现的次数。模式串有两种类型，0类型代表可以有重叠，1类型代表不能有重叠。模式串可能出现重复。
分析
算是AC自动机的模板题？
因为模式串可以重复，所以如果直接插入并且用val数组来保存模式串的编号的话，后面出现的会把前面出现的给覆盖。所以我这里用了一个map来保存每个模式串在trie中的编号。
如何处理1类型不能有重叠的情况？对于1类型的每个模式串，记录一下它的长度和上次匹配到的位置。当再次匹配到这个模式串的时候，看一下这次的位置和上次位置的差有没有大于它的长度，如果大于，则说明这个可以选择不会重叠。
我们在插入模式串的时候不区分是哪种类型，在进行find的时候也不进行区分，找到一个模式串以后，同时更新两种类型。只在最后输出的时候区分一下。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <queue> 6 #include <map> 7 8 using namespace std; 9 const int maxnode=700000; 10 const int sigma_size=26; 11 const int maxs=100000+100; 12 char T[maxs],P[maxs][20],type[maxs]; 13 map<string,int>ms; 14 int kase; 15 struct AC_Automata{ 16 int ch[maxnode][sigma_size],val[maxnode],cnt[maxnode][2],tim[maxnode]; 17 int f[maxnode],last[maxnode],len[maxnode]; 18 int sz; 19 void init(){ 20 sz=1; 21 memset(ch[0],0,sizeof(ch[0])); 22 memset(cnt,0,sizeof(cnt)); 23 memset(tim,0,sizeof(tim)); 24 val[0]=0; 25 ms.clear(); 26 } 27 void insert(char *s){ 28 int n=strlen(s),u=0; 29 for(int i=0;i<n;i++){ 30 int c=s[i]-'a'; 31 if(!ch[u][c]){ 32 ch[u][c]=sz; 33 memset(ch[sz],0,sizeof(ch[sz])); 34 val[sz++]=0; 35 } 36 u=ch[u][c]; 37 } 38 val[u]=1; 39 len[u]=n; 40 string S=(string)s; 41 ms[S]=u; 42 } 43 void getFail(){ 44 queue<int>q; 45 f[0]=last[0]=0; 46 for(int i=0;i<sigma_size;i++){ 47 int u=ch[0][i]; 48 if(u){ 49 q.push(u); 50 f[u]=last[u]=0; 51 } 52 } 53 while(!q.empty()){ 54 int r=q.front();q.pop(); 55 for(int i=0;i<sigma_size;i++){ 56 int u=ch[r][i]; 57 if(!u)continue; 58 q.push(u); 59 int v=f[r]; 60 while(v&&!ch[v][i])v=f[v]; 61 f[u]=ch[v][i]; 62 last[u]=val[f[u]]?f[u]:last[f[u]]; 63 } 64 } 65 } 66 void print(int i,int pos){ 67 if(val[i]){ 68 cnt[i][0]++; 69 if(tim[i]+len[i]<=pos){ 70 cnt[i][1]++; 71 tim[i]=pos; 72 } 73 print(last[i],pos); 74 } 75 } 76 void find(char *s){ 77 int n=strlen(s),j=0; 78 for(int i=0;i<n;i++){ 79 int c=s[i]-'a'; 80 while(j&&!ch[j][c])j=f[j]; 81 j=ch[j][c]; 82 if(val[j]) 83 print(j,i+1); 84 else if(last[j]) 85 print(last[j],i+1); 86 } 87 } 88 }ac; 89 int n; 90 int main(){ 91 kase=0; 92 while(scanf("%s",T)!=EOF){ 93 ++kase; 94 scanf("%d",&n); 95 ac.init(); 96 for(int i=1;i<=n;i++){ 97 scanf("%d %s",&type[i],P[i]); 98 ac.insert(P[i]); 99 } 100 ac.getFail(); 101 ac.find(T); 102 printf("Case %d\n",kase); 103 for(int i=1;i<=n;i++){ 104 string S=(string)P[i]; 105 int u=ms[S]; 106 printf("%d\n",ac.cnt[u][type[i]]); 107 // printf("%d\n",u); 108 } 109 printf("\n"); 110 } 111 return 0; 112 }