题意：统计其中一个子串的出现次数
题解：即KMP算法中j==m的次数
//作者:1085422276 #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> //#include<bits/stdc++.h> #include <map> #include <stack> typedef long long ll; using namespace std; const int inf = 10000000; inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } ll exgcd(ll a,ll b,ll &x,ll &y) { ll temp,p; if(b==0) { x=1; y=0; return a; } p=exgcd(b,a%b,x,y); temp=x; x=y; y=temp-(a/b)*y; return p; } //******************************* int p[1000001]; int main() { int T; scanf("%d",&T); while(T--) { string a,b; cin>>b>>a; a=" "+a; b=" "+b; int m=b.length(); int n=a.length(); n--,m--; memset(p,0,sizeof(p)); int j=0; for(int i=2;i<=m;i++) { while(j>0&&b[j+1]!=b[i])j=p[j]; if(b[j+1]==b[i])j++; p[i]=j; } int ans=0; j=0; for(int i=1;i<=n;i++) { while(j>0&&b[j+1]!=a[i])j=p[j]; if(b[j+1]==a[i])j++; if(j==m){ ans++; } } cout<<ans<<endl; } return 0; }