KMP

• 在text串中找有无pattern子串
• 参考：如何更好地理解和掌握 KMP 算法? - 海纳的回答 - 知乎 https://www.zhihu.com/question/21923021/answer/281346746

匹配

• 部分匹配表（Partial Match Table, PMT）的数组：qmt[i-1]表示字符串前i个字符（s[0]~s[i-1]）的前缀与后缀重复的部分的长度为qmt[i-1]那么长。
• 在下图中qmt[i-1] = 4
• 当text[i]与pattern[j]不匹配时，i指针前j个字符都匹配上了。
  • 根据PMT的定义，pattern中 j前pmt[j-1]个字符与pattern中从0开始的pmt[j-1]的字符是一样的。
  • 所以不需要再从头匹配，pattern的j指针直接跳转到pmt[j-1]即可继续匹配
• 

求next数组

• 由于在j位失配，那么影响j指针回溯位置的其实是j-1的PMT值，所以为了编程方便，将PMT数组向后偏移一位，得到新数组next数组。
  • 这样在j位失配后，直接跳转到next[j]即可（比pmt[j-1]方便）
  • 第0位的next值为-1：为了编程方便
  • 
• 求next数组：其实就是pattern与pattern匹配
• 
• 
• 
• 
• 

模板

void getNext(char * p, int * nxt){
	nxt[0] = -1;
	int i=0, j=-1;
	// 注意这里跳出的条件是i==strlen(p)
	// 所以其实只要扫一遍pattern就可以求出nxt数组 
	// 要区别kmp 
	while(i<strlen(p)){
		if(j==-1||p[i]==p[j]){
			// 注意是先自增再赋值nxt数组
			// 这样可以让pmt偏移一位成为nxt 
			j++;
			i++;
			nxt[i] = j;
		}
		else{
			j = nxt[j];
		}
	}
}

int kmp(char * t, char * p){
	int i = 0;
	int j = 0;
	while(i<strlen(t)&&j<strlen(p)){
		if(j==-1||t[i]==p[j]){
			i++;
			j++;
		}
		else j = nxt[j];
	}
	// 匹配完了pattern 
	// 返回在text中找到的起始位置 
	// 注意这里的pattern和text的下标都是从0开始的 
	if(j==strlen(p)){
		return i-j;
	}
	// 找不到返回-1 
	else return -1;
}

【字符串匹配】KMP算法板子

原文：https://www.cnblogs.com/xuwanwei/p/14673049.html