KMP：子串在对父串每一次匹配失败时，右移位数的优化。
右移位数 = 已匹配的字符数 - 对应的部分匹配值
前缀：字串中，除了最后一个字符，包含第一个字符的全部字串组合
后缀：字串中，除了第一个字符，包含最后一个字符的全部字串组合
部分匹配值：前缀和后缀所有字串中包含有共同字符的字符个数
部分匹配表：首字符开始，下标对应于KMP数组下标，每个KMP数组元素值为首字符到当前字符字串的匹配值。
eg：根据子串KMP推导右移个数
ETCABCDABETC
ABCDABD
子串第7位匹配失败，查表PMT[6]，右移位数 = 6 - PMT[6] = 4，右移4位。
eg：手动推导子串KMP
子串：ABCDABD
KMP实现：
1. PMT[0] = 0；子串第一个字符组成的字串的前后缀匹配值都为0。如果可选L都为0，直接对比首尾元素。
2. 从PMT[1]开始推导，LL为当前计算子串的前后交集元素最长长度，如果sub_str[LL] = sub_str[i]，则当前LL加 1
3. 如果sub_str[LL] != sub+str[i]，则LL = KMP[LL - 1]，直到sub_str[LL] = sub_str[i]。
实现代码：
int* String::make_mtp(const char* up_str) { int ll = 0; int len = strlen(up_str); int* pmt = static_cast<int*>(malloc(sizeof(int) * len)); if(pmt != NULL) { pmt[0] = 0; for(int i = 0; i < len; i++) { while((ll > 0) && (pmt[ll] != pmt[i])) { ll = pmt[ll - 1]; } if(pmt[ll] == pmt[i]) { ++ll; } } } return pmt; } int String::kmp(const char* up_str, const char* sub_str) { int ret = -1; int up_len = strlen(up_str); int sub_len = strlen(sub_str); int* pmt = make_mtp(up_str); if((pmt != NULL && up_len >= sub_len && sub_len > 0)) { for(int i = 0, j = 0;i < up_len ;i++) { while(j > 0 && up_str[i] != sub_str[j]) { j = pmt[j - 1]; } if(up_str[i] == sub_str[j]) { j++; } if(j == sub_len) { ret = i + 1 - sub_len; break; } } } free(pmt); return ret; }
原文：https://www.cnblogs.com/zsy12138/p/12285763.html