kmp算法

const int MAX=10010;
int Next[MAX];

void getNext(char s[], int n) {
	int j = -1;
	/* Next数组的起始索引，是一个无效的索引
	   表示最长公共前后缀前缀的最后一位的下标
	*/
	Next[0] = -1;
	for (int i=1; i<n; ++i) {
		while (j != -1 && s[i]!=s[j+1]) j = Next[j];
		if (s[i] == s[j+1]) j ++;
		Next[i] = j;
	}
}

bool kmp(char *text, char *pattern) {
	int n = strlen(text), m = strlen(pattern);
	getNext(pattern, m);
	int j = -1;
	for (int i=0; i<n; ++i) {
		while (j != -1 && text[i] != pattern[j+1]) j = Next[j];
		if (text[i] == pattern[j+1]) j ++;
		if (j == m-1) return true;
	}
	return false;
}