ZOJ - 3228 Searching the String
题目链接：https://zoj.pintia.cn/problem-sets/91827364500/problems/91827367940
题意：（多组输入）给出一个字符串和n个模式串，模式串前的数字 0 代表可以重叠，1代表不能重叠，求每个模式串出现的次数。
题解：算是AC自动机的板子题。在query的时候需要多判断一下不能重叠的情况，用last数组记录上一个串出现的位置，比较两个模式串的距离是否小于串的长度，小于的话就跳过，否则就+1；
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 6e5+10; 5 const int N = 30; 6 int a[maxn],b[maxn][2],last[maxn]; 7 8 struct tire{ 9 int nxt[maxn][N],fail[maxn],c[maxn],end[maxn],tot,root; 10 int newNode(){ 11 for(int i=0;i<26;i++) nxt[tot][i] = -1; 12 c[tot++]=0; 13 return tot-1; 14 } 15 void Init(){ 16 tot = 0; 17 root = newNode(); 18 } 19 void Insert(char *buf,int id){ 20 int len = strlen(buf),i,u = root; 21 for(i=0;i<len;i++){ 22 int x = buf[i]-'a'; 23 if(nxt[u][x]==-1) nxt[u][x] = newNode(); 24 c[nxt[u][x]]=c[u]+1; 25 u = nxt[u][x]; 26 } 27 end[id] = u; 28 } 29 void build(){ 30 queue <int> q; 31 fail[root] = root; 32 for(int i=0;i<26;i++){ 33 if(nxt[root][i]==-1) nxt[root][i] = root; 34 else{ 35 fail[nxt[root][i]] = root; 36 q.push(nxt[root][i]); 37 } 38 } 39 while(!q.empty()){ 40 int now = q.front(); 41 q.pop(); 42 for(int i=0;i<26;i++){ 43 if(nxt[now][i]==-1) nxt[now][i] = nxt[fail[now]][i]; 44 else{ 45 fail[nxt[now][i]] = nxt[fail[now]][i]; 46 q.push(nxt[now][i]); 47 } 48 } 49 } 50 } 51 void query(char *buf){ 52 int len = strlen(buf),now = root; 53 for(int i=0;i<len;i++){ 54 int x = buf[i]-'a'; 55 now = nxt[now][x]; 56 int tmp = now; 57 while(tmp!=root){ 58 b[tmp][0]++; 59 if(i-last[tmp]>=c[tmp]){ 60 b[tmp][1]++; 61 last[tmp]=i; 62 } 63 tmp=fail[tmp]; 64 } 65 } 66 } 67 }ac; 68 69 char s1[10]; 70 char s[100100]; 71 72 int main() 73 { 74 int t=0,n; 75 while(scanf("%s",s)!=EOF){ 76 t++; 77 scanf("%d",&n); 78 ac.Init(); 79 for(int i=0;i<n;i++){ 80 scanf("%d",&a[i]); 81 scanf("%s",s1); 82 ac.Insert(s1,i); 83 } 84 ac.build(); 85 memset(last,-1,sizeof(last)); 86 memset(b,0,sizeof(b)); 87 ac.query(s); 88 printf("Case %d\n",t); 89 for(int i=0;i<n;i++){ 90 printf("%d\n",b[ac.end[i]][a[i]]); 91 } 92 printf("\n"); 93 } 94 return 0; 95 }
