2017-08-13 19:31:47
writer：pprp
对kmp算法有了大概的了解以后，虽然还不够深入，但是已经可以写出来代码，（可以说是背会了）
所以这道题就作为一个模板，为大家使用吧。
题目大意：给你一个子串P和一个主串S，求在主串中有多少个子串？
代码如下：（需要注意的点我都标记好了，两个函数可以直接用）
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring> using namespace std;
int ans;
const int maxn = ;
int next[maxn];
char S[maxn],P[maxn]; //构造next数组
void get_next()
{
int i = ;
int j = -; int lenp = strlen(P); //要用额外变量，如果写在while循环中就会TLE next[] = -; while(i < lenp)
{
if(j == - || P[i] == P[j])
{
i++;
j++;
next[i] = j;
}
else
j = next[j];
}
} //开始模式匹配
void kmp()
{
int i = ;
int j = ; //要用额外变量，如果写在while循环中就会TLE
int lens = strlen(S);
int lenp = strlen(P); get_next(); //这个构造不能忘记写 while(i < lens && j < lenp)
{
if(j == - || P[j] == S[i])
{
i++;
j++;
}
else
j = next[j];
if(j == lenp)
{
ans++;
j = next[j];
}
}
}
int main()
{
int cas;
cin >> cas; while(cas--)
{
ans = ;
memset(next,,sizeof(next));
scanf("%s%s",P,S);
kmp();
cout << ans << endl;
}
return ;
}