题目大意

给出n对字符串求出b在a中出现了多少次

思路

跑n遍kmp

#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#define maxn 10000001
using namespace std;
int p[maxn];
char s1[maxn],s2[maxn];
int kmp(char a[maxn],char b[maxn])
{
    int n=strlen(a),m=strlen(b);
    int j=-1,ans=0;
    for (int i=0;i<n;i++)
    {
        while (a[i]!=b[j+1]&&j!=-1) j=p[j];
        if (a[i]==b[j+1]) j++;
        if (j==m-1)
        {
            ans++;
            j=p[j];
        }
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    for (int o=1;o<=t;o++)
    {
        scanf("%s%s",s2,s1);
        int len=strlen(s2);
        p[0]=-1;
        int j=-1;
        for (int i=1;i<len;i++)
        {
            while (s2[i]!=s2[j+1]&&j!=-1) j=p[j];
            if (s2[i]==s2[j+1])
                j++;
            p[i]=j;
        }
        printf("%d\n",kmp(s1,s2));
    }
}