【模板】KMP字符串匹配

给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。

为了减少骗分的情况，接下来还要输出子串的前缀数组next。

朴素算法：暴力判断……复杂度为(O(m(n-1)))

优化朴素算法：找到不同匹配点立即退出匹配 当然 这样最坏情况也会卡到(O(m(n-1)))。

（于是就被迫来学KMP）

思路神奇的算法……模式串自己匹配自己）

定义：失配 用模式串匹配原串 判到一个位置不能匹配就是失配

如果我们扫原串的时候发现在某状态失配了的话，可以通过上面说的模式串自己匹配自己，来判断下一个可能的状态应该转移到哪里。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define MAXN 1000005
#define scanf(a) scanf("%d",&a)
#define print(a) printf("%d",a)
#define print_(a) printf("%d ",a)
#define printn(a) printf("%d
",a)
#define endl printf("
");
#define IMS char
using namespace std;

IMS a[MAXN],b[MAXN];
int kmp[MAXN],lena,lenb;

void init()
{
	cin>>a+1;
	cin>>b+1;
}
void KMP()
{
	lena=strlen(a+1);
	lenb=strlen(b+1);
	int j=0;
	for (int i=2;i<=lenb;i++)
	{
		while (j&&b[i]!=b[j+1])
		{
			j=kmp[j];
		}
		if (b[j+1]==b[i])
		{
			j++;
		}
		kmp[i]=j;
	}
}
void start()
{
	int j=0;
	for (int i=1;i<=lena;i++)
	{
		while (j>0&&b[j+1]!=a[i])
		{
			j=kmp[j];
		}
		if (b[j+1]==a[i])
		{
			j++;
		}
		if (j==lenb)
		{
			print(i-lenb+1);
			endl;
			j=kmp[j];
		}
	}
	for (int i=1;i<=lenb;i++)
	{
		print_(kmp[i]);
	}
}

int main()
{
	init();
	KMP();
	start();
	return 0;
}