首先说这个题目的意思，就是去匹配然后找出最多能够匹配的次数
这个题一开始直接暴力没有过，就感觉这应该是我没有接触过的算法，训练赛结束后去学习，知道了关于字符串的kmp算法，说实话对于这个算法了解还不够很详细，
先学习了这个板子，以我现在的水平去了解这个算法有点难度，关于字符串的那个覆盖问题，有点难以理解，以后了解更多会回来再更这一篇博客的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <math.h>
#include <stack>
#define LL long long
using namespace std;
const int maxn = 100000 + 10;
int next[maxn];
const int INF = 0x3f3f3f3f;
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
char s[maxn*10],p[maxn];
int lens,lenp;
void getnext()
{
int i = 0,j = -1;
next[0] = -1;
while(i != lenp)
{
if(j == -1 || s[i] == s[j])
next[++i] = ++j;
else
j = next[j];
}
}
int kmp()
{
int i = 0,j = 0,count = 0;
while(i != lens && j != lenp)
{
if(s[i] == p[j] || j == -1)
++i,++j;
else
j = next[j];
if(j == lenp)
{
count++;
j = next[j];
}
}
return count;
}
int main()
{
int ncase;
int len;
int ans;
cin>>ncase;
while(ncase--)
{
scanf("%s%s",p,s);
lens = strlen(s);
lenp = strlen(p);
getnext();
ans = kmp();
printf("%d\n",ans);
}
return 0;
}
