KMP主要是利用匹配失败的串的相同前缀。

string t;
string s;
int nxt[maxn];//nxt数组求匹配串的前缀的那个值

void prekmp(string x) {//处理匹配串
	memset(nxt, 0, sizeof(nxt));
	int i, j;//前后指针
	j = nxt[0] = -1;//头指针
	i = 0;//后指针
	int m = x.length();
	while (i < m) {//处理完全部的
		while (-1 != j && x[i] != x[j])j = nxt[j];//如果不等 往前回溯 直到相等或者头指针到头
		nxt[++i] = ++j;//更新下标
	}
}

int kmp(string x, string y) {//x是模式串 y是主串
	int i, j;
	int ans = 0;
	prekmp(x);//预处理
	int m = x.length();
	int n = y.length();
	i = j = 0;//一个指向匹配串 一个指向模式串
	while (i < n) {
		while (-1 != j && y[i] != x[j]) j = nxt[j];//更新匹配位置
		i++; j++;//向后推移一位
		if (j >= m) {//这部分可灵活变化
			ans = 1;
			break;
		}
	}
	return ans;
}