KMP匹配

定义nextt[i] 为 模式串b中的第i个数字的真前后缀最大公共子串长度

**eg: ababac 下标从1开始，nextt[1] = 0, next[2] = 0, next[3] = 1（因为b[1]和b[3]是此时相同前后缀的最大长度）......依次类推 **

至于kmp的原理简单来说就是在朴素算法的基础上在匹配a[i] 和 b[j]时，如果不等，每次由模式串整体向后移一位，变成了只动模式串，将j变成了nextt[j]，然后再去匹配a[i] 和 b[j],这样可以极大的提升匹配效率，因为显然j到nextt[j]中间这段是无法匹配成功的。 很多博客写得更加清楚可以参考一下。

简单点理解kmp就是，首先令文本串a不动，接着不断地去匹配a[i] 与 b[j]，通过j = nextt[j] 的操作我们删去了中间必定失配的过程。

代码示例：

//#pragma comment(linker,   "/STACK:10240000000000,10240000000000")
//#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define For(i,a,b) for (int i=(a);i<=(b);++i)
#define Fod(i,b,a) for (int i=(b);i>=(a);--i)
#define mls multiset
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pob pop_back
#define itt iterator
#define lowbit(x) x & (-x)
#define clr(x) memset(x, 0, sizeof(x));

typedef long long ll;
typedef unsigned long long ull;
		
using namespace std;
const int MAXN = 0x7fffffff;
const int MOD = 1000000007;
const ll MOD1 = 212370440130137957ll;

const int N = 1e6 + 5;

int nextt[N];

char a[N], b[N];

int alen, blen;

void getnext(int len) // 求nextt数组 模式串与自己匹配
{
	for(int i = 2, j = 0; i <= len; i++) //j为
	{
		while(j && b[j + 1] != b[i]) j = nextt[j]; //如果无法匹配，最大的子前后缀公共字符串长度一定为nextt[j]。
		if(b[j + 1] == b[i]) j++;//前后缀匹配成功, 长度+1
		nextt[i] = j;
	}
}

void kmp(int alen, int blen)  //文本串与模式串匹配
{
	for(int i = 1, j = 0; i <= alen; i++)
	{
		while(j && b[j + 1] != a[i]) j = nextt[j];
		if(b[j + 1] == a[i]) j++;
		if(j == blen)
		{
			cout << i - blen + 1 << endl;
			j = nextt[j];
		}
	}
}

int main ()
{	
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> a + 1 >> b + 1;

	alen = strlen(a + 1);
	blen = strlen(b + 1);

	getnext(blen);
	kmp(alen, blen);

	For(i, 1, blen) cout << nextt[i] << " ";
	return 0;
}