关于KMP算法讲解:https://blog.csdn.net/v_july_v/article/details/7041827
这里只当作模板使用
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
char s[N], p[N];
int nexts[N];
void getnext()
{
int plen = strlen(p); // 字串长度
nexts[0] = -1; //
int k = -1;
int j = 0;
while(j < plen - 1)
{
if(k == -1 || p[j] == p[k])
{
k ++;
j ++;
nexts[j] = k;
}
else
k = nexts[k];
}
}
int kmp()
{
int i = 0;
int j = 0;
int slen = strlen(s);
int plen = strlen(p);
while(i < slen && j < plen)
{
// j == -1 || 匹配成功
if(j == -1 || s[i] == p[j])
{
i ++;
j ++;
}
else // 匹配失败
j = nexts[j];
}
if(j == plen)
return i - j; // 返回匹配成功位置的下标
else
return -1; // 表示未匹配成功
}
int main()
{
scanf("%s %s", s, p);
// printf("%s %s\n", s, p);
memset(nexts, 0, sizeof(nexts));
getnext();
int index = kmp();
printf("%d\n", index);
return 0;
}