KMP
KMP：子串在對(duì)父串每一次匹配失敗時(shí)，右移位數(shù)的優(yōu)化。
右移位數(shù) = 已匹配的字符數(shù) - 對(duì)應(yīng)的部分匹配值
前綴：字串中，除了最后一個(gè)字符，包含第一個(gè)字符的全部字串組合
后綴：字串中，除了第一個(gè)字符，包含最后一個(gè)字符的全部字串組合
部分匹配值：前綴和后綴所有字串中包含有共同字符的字符個(gè)數(shù)
部分匹配表：首字符開(kāi)始，下標(biāo)對(duì)應(yīng)于KMP數(shù)組下標(biāo)，每個(gè)KMP數(shù)組元素值為首字符到當(dāng)前字符字串的匹配值。
eg：根據(jù)子串KMP推導(dǎo)右移個(gè)數(shù)
ETCABCDABETC
ABCDABD
子串第7位匹配失敗，查表PMT[6]，右移位數(shù) = 6 - PMT[6] = 4，右移4位。
eg：手動(dòng)推導(dǎo)子串KMP
子串：ABCDABD
KMP實(shí)現(xiàn)：
1. PMT[0] = 0；子串第一個(gè)字符組成的字串的前后綴匹配值都為0。如果可選L都為0，直接對(duì)比首尾元素。
2. 從PMT[1]開(kāi)始推導(dǎo)，LL為當(dāng)前計(jì)算子串的前后交集元素最長(zhǎng)長(zhǎng)度，如果sub_str[LL] = sub_str[i]，則當(dāng)前LL加 1
3. 如果sub_str[LL] != sub+str[i]，則LL = KMP[LL - 1]，直到sub_str[LL] = sub_str[i]。
實(shí)現(xiàn)代碼：
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; }
浙公網(wǎng)安備 33010602011771號(hào)