目录
题目描述
给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 P 在字符串 S 中多次作为子串出现。
求出模式串 P 在字符串 S 中所有出现的位置的起始下标。
输入格式
第一行输入整数 N，表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M，表示字符串 S 的长度。
第四行输入字符串 S。
输出格式
共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。
数据范围
1≤N≤1e5
1≤M≤1e6
输入样例
3
aba
5
ababa输出样例
0 2思路解析
下面给出KMP的算法思路：
上面的图应该能让您对KMP有个初步了解，接下来我将提供KMP字符串匹配的代码，并添加较为详细的注释来帮助您理解，并且我会用相同的颜色将代码与注释对应起来，紧接着我将给出最终纯享版代码，为了方便大家对题目有一个很好的调试，
题目连接：//http://47.110.135.197/problem.php?id=6771
#include<iostream>
#include<string>
using namespace std;
const int N=100000;
int ne[N];
int main()
{
int n,m;
string p,s;
cin>>n>>p>>m>>s;
下面红颜色的注释对应图解二
//求解next数组，next数组是当前字符最长的相等前缀和后缀的长度
//例如“aadaaf”的每个字符的前后缀长度分别为“0，1，0，1，2，0”
//这里解释第二个和第三个即可理解含义：第二个的字符是a，则前两个字符里面，相等：前缀为a，后缀也为a，所以为1
//第五个字符，前五个字符里面，相等：前缀为aa，后缀也为aa，所以为2
//输入的s字符串，第一个字符下标从0开始
//下面的过程对应图解三
ne[0]=0;//所以第一个字符的最长前缀和后缀一定为0
int j=0;//j是前缀末尾
for(int i=1;i<=n;i++)//i是后缀末尾，由于要比较前后缀，所以将j初始化为0，将i初始化为1
{
//当前后缀不相同时，就让j回到找前面所有字符的相同前后缀，这样即可继续匹配，即next数组的j-1下标
while(j>0&&p[i]!=p[j])//当p[i]==p[j]时执行下面的操作，当j到0的时候就不用回退了
{
j=ne[j-1];//回退到前面所有字符前后缀相同的下标
}
//当前后缀相同时
if(p[i]==p[j]) j++;//前缀末尾就加1，说明相同前后缀的长度多了1
ne[i]=j;//前i个字符里面，前后缀相同的长度就是j
}
//下面的过程对应图解一
for(int i=0,j=0;i<m;i++)//此时i和j分别代表s和p的遍历下标
{
while(j>0&&s[i]!=p[j]) j=ne[j-1];//当遍历到两字符串不相等时，j进行回退到前后缀相同的位置下标
if(s[i]==p[j]) j++;//如果相等，继续匹配下一个字符
if(j==n)//当j遍历到p的末尾时，说明模式串完全匹配
//这里为什么不是n-1呢，因为n-1的时候也要验证一下，j++就变成n了
{
cout<<i-n+1<<" ";//用当前的i-模式串的长度+1就是刚出现时的下标
j=ne[j-1];//然后j回退，继续匹配下一个出现的位置
}
}
return 0;
}
纯享版代码
#include<iostream>
#include<string>
using namespace std;
const int N=100000;
int ne[N];
int main()
{
int n,m;
string p,s;
cin>>n>>p>>m>>s;
ne[0]=0;
int j=0;
for(int i=1;i<=n;i++)
{
while(j>0&&p[i]!=p[j])
{
j=ne[j-1];
}
if(p[i]==p[j]) j++;
ne[i]=j;
}
for(int i=0,j=0;i<m;i++)
{
while(j>0&&s[i]!=p[j]) j=ne[j-1];
if(s[i]==p[j]) j++;
if(j==n)
{
cout<<i-n+1<<" ";
j=ne[j-1];
}
}
return 0;
}