Oulipo POJ

题目：查找一个模式串在其他串中出现的次数

KMP算法详解链接：https://blog.csdn.net/qq_37969433/article/details/82947411

 1 #include<iostream>
 2 #include<map>
 3 #include<string.h>
 4 using namespace std;
 5 #define MAXN 1000059
 6 string t,s;
 7 int l1,l2;
 8 int nxt[MAXN];
 9 void getnxt(){
10     int j=0,k=-1;
11     nxt[0]=-1;
12     while(j<l2){
13         if(k==-1||t[j]==t[k]){
14             nxt[++j]=++k;
15         }
16         else{
17             k=nxt[k];
18         }
19     }
20 }
21 int kmp(){
22     int ans=0;
23     int j=0;
24     if(l1==1&&l2==1){
25         if(s[0]==t[0]){
26             return 1;
27         }
28         return 0;
29     }
30     getnxt();
31     for(int i=0;i<l1;i++){
32         //直到找到第一个适配首字母 
33         while(j>0&&s[i]!=t[j]){
34             j=nxt[j];
35         }
36         if(s[i]==t[j]){
37             j++;
38         }
39         if(j==l2){
40             ans++;
41             j=nxt[j];
42         }
43     }
44     return ans;
45 }
46 int main(){
47     ios::sync_with_stdio(0);
48     cin.tie(0);
49     int T;
50     cin>>T;
51     while(T--){
52         cin>>t>>s;
53         l1=s.size();
54         l2=t.size();
55         cout<<kmp()<<endl;
56     }
57     return 0;
58 }