KMP算法模板

参考《数据结构 C语言版（严蔚敏）》中的代码，根据C++ string类的操作略作修改。

建议背下来，直接套用！

#include 
using namespace std;
const int M = 100;
int n[M] = { -1 };
void get_n(string t) {
	int i = 0, j = -1;
	while (i < t.size()) {
		if (j == -1 || t[i] == t[j]) {
			if (t[++i] != t[++j])n[i] = j;
			else n[i] = n[j];
		}
		else j = n[j];
	}
}
int KMP(string s, string t, int pos) {
	//pos从0开始，返回子串第一次出现的位置
	int i = pos, j = 0, slen = s.size(), tlen = t.size();
	while (i < slen && j < tlen) {
		if (j == -1 || s[i] == t[j]) {
			i++, j++;
		}
		else j = n[j];
	}
	if (j == tlen)return i - j;
	return -1;
}