数据结构——KMP算法

831. KMP字符串
给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 P 在字符串 S 中多次作为子串出现。
求出模式串 P 在字符串 S 中所有出现的位置的起始下标。
输入格式
第一行输入整数 N，表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M，表示字符串 S 的长度。
第四行输入字符串 S。
输出格式
共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。
数据范围
1≤N≤10^5
1≤M≤10^6
输入样例：
3
aba
5
ababa
输出样例：
0 2

暴力解法  时间复杂度平方级别会超时

int i,j;
	for(i=1;i<=m-n+1;i++){
		for(j=1;j<=n;j++){
			if(s[i]!=s[j]) break;
		}
		if(j>m) cout<<i<<" ";
	}

KMP算法
1.取最长的相等前后缀，可以保证不漏解。
2.通过模式串前后缀的自我匹配的长度，计算next函数，给指针打一张表，失配时就跳到next[j]的位置继续匹配。

next函数
next[i]表示模式串P[1，i]中相等前后缀的最长长度。

next函数
next[i]表示模式串P[1，i]中相等前后缀的最长长度。
双指针：i扫描模式串，j扫描前缀。
初始化，ne[1]=0，i=2，j=0。
每轮for循环，i向右走一步。
1.若P[i]！=P[j+1]，让j回跳到能匹配的位置，如果找不到能匹配的位置，j回跳到0。
2.若P[i]==P[j+1]，让j+1，指向匹配前缀的末尾。
3.next[i]等于j的值。

int ne[N];//最长相等真前后缀的长度
void do_next() {
   ne[1]=0;//初始化数据
   for(int i=2,j=0;i<=n;i++){//i扫描字符串 j扫描前缀
     while(j && p[i]!=p[j+1]) j=ne[j];//回跳
     if(p[i]==p[j+1]) j++;//相同 增加一个
     ne[i]=j;//记录P[1，i]中相等前后缀的最长长度
   }
 }

j指针所走的总步数就决定了总的执行次数。
每轮for，j至多+1，那么j一共向右至多走n步，往左跳的步数加起来不会超过n步，否则j变为负数，故j的总步数不会超过2n。例a…ab。所以时间复杂度O(n)。

模式串与主串匹配
双指针：i扫描主串，j扫描模式串。
初始化，i=1，j=0。每轮for，i向右走一步。
1.若S[i]！=P[j+1]，让j回跳到能匹配的位置，如果找不到能匹配的位置，j回跳到0。
2.若S[i]==P[j+1]，让j向右走一步。
3.若匹配成功，输出匹配位置。

void do_KMP(){
   for(int i=1,j=0;i<=m;i++){
     while(j &&s[i]!=p[j+1]) j=ne[j]; //不同 j指针回跳
     if(s[i]==p[j+1]) j++; //相同 j指针右移
     if(j==n) printf("%d ",i-n+1);//匹配成功 输出位置
   }
 }

j指针所走的总步数就决定了总的执行次数。
每轮for，j至多+1，那么j一共向右至多走m步，往左跳的步数加起来不会超过m步，否则j变为负数，故j最多走2m步。例a……a，ab。所以时间复杂度0(m)。

//完整参考代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e6+5;
int m,n;
char s[N],p[N];
int ne[N];//最长相等的真前后缀的长度
void do_next(){
	ne[1]=0;
	for(int i=2,j=0;i<=n;i++){
		while(j&&p[i]!=p[j+1])j=ne[j];
		if(p[i]==p[j+1]) j++;
		ne[i]=j;
	}
}
void do_KMP(){
	for(int i=1,j=0;i<=m;i++){
		while(j &&s[i]!=p[j+1]) j=ne[j];
		if(s[i]==p[j+1]) j++;
		if(j==n) printf("%d ",i-n);//注意题目当中的下标起点是0还是1
	}
}
int main()
{
	cin>>n;
	cin>>p+1;
	cin>>m;
	cin>>s+1;
	do_next();
	do_KMP();
    return 0;
}