kmp字符串匹配原理参考博客：https://blog.csdn.net/bqw18744018044/article/details/90516750

代码如下：（写一遍模板）

#include
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
#define pf printf
#define mem(a,b) memset(a,b,sizeof(a))
#define prime1 1e9+7
#define prime2 1e9+9
#define pi 3.14159265
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define scand(x) scanf("%llf",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define scan(a) scanf("%d",&a)
#define dbg(args) cout<<#args<<":"<<args<<endl;
#define inf 0x3f3f3f3f
#define maxn 1000010
int n,m,t;
int nxt[maxn];//nxt数组:i位置失配后nxt[i]就是下一个该匹配的字符
char s[maxn],p[maxn];//主串和模式串
void getnxt()
{
int plen=strlen(p);
int i=-,j=;
nxt[]=-;
while(j<plen)
{
if(i==-||p[i]==p[j])
{
i++,j++;
if(p[i]!=p[j])nxt[j]=i;//如果两者相等则在失配情况下转到i位置之后照样会失配
else nxt[j]=nxt[i];
}
else i=nxt[i];//失配后在前的i指针继续寻找匹配项
}
}
int kmp(char *s,char *p)
{
int slen=strlen(s);
int plen=strlen(p);
int cnt=;
int i=,j=;
while(i<slen)
{
if(j==-||s[i]==p[j])i++,j++;//j==-1的时候说明s[i]这一位是不可能正确匹配的
else j=nxt[j];
if(j==plen)cnt++;
}
return cnt;
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
std::ios::sync_with_stdio(false);
scan(t);
while(t--)
{
scanf("%s %s",p,s);
getnxt();
pf("%d\n",kmp(s,p));
}
}