學(xué)習(xí)筆記三 KMP算法介紹
本題來(lái)自：力扣28.實(shí)現(xiàn)strStr()
題目描述
簡(jiǎn)單來(lái)說(shuō)，題目要求是從一個(gè)字符串 haystack 中找到另一個(gè)字符串 needle 出現(xiàn)的第一個(gè)位置。如果按暴力解法楷拳，題目解答很容易想到是 O(m * n) 的時(shí)間復(fù)雜度讨衣。那么，有沒(méi)有一種解法没炒，它的時(shí)間復(fù)雜度可以降到 O(m + n) 呢涛癌？
有！這就是我們接下來(lái)要介紹的 KMP 算法
KMP的主要思想
- KMP的主要思想是：當(dāng)出現(xiàn)字符串不匹配時(shí)送火，可以知道一部分之前已經(jīng)匹配的文本內(nèi)容拳话，避免從頭再去做匹配了。這也是我們能將時(shí)間復(fù)雜度降低的本質(zhì)种吸。
KMP實(shí)現(xiàn)的關(guān)鍵步驟
一弃衍、構(gòu)建 next 數(shù)組
先來(lái)解釋幾個(gè)名詞：前綴，后綴骨稿，最長(zhǎng)公共前后綴笨鸡，前綴表
前綴：不包含最后一個(gè)字符的，并以第一個(gè)字符為開(kāi)頭的所有子字符串
后綴：不包含第一個(gè)字符的坦冠，并以最后一個(gè)字符為結(jié)尾的所有子字符串
最長(zhǎng)公共前后綴：對(duì)于一個(gè)字符而言形耗，最長(zhǎng)的相同的前綴后綴
前綴表：前綴表是記錄下標(biāo) i 之前（包括 i）的字符串中，有多大長(zhǎng)度的最長(zhǎng)公共前后綴
而我們要構(gòu)建的 next 數(shù)組辙浑，就是所謂的前綴表激涤。
KMP 算法實(shí)現(xiàn)的第一個(gè)難點(diǎn)便是 next 數(shù)組的構(gòu)建求解，即 對(duì)于一個(gè)子串，如何去求它的最長(zhǎng)公共前后綴倦踢？
構(gòu)造 next 數(shù)組其實(shí)就是計(jì)算短串的前綴表的過(guò)程送滞，其關(guān)鍵步驟主要有如下三步：
- 初始化
- 處理前后綴不相同的情況
- 處理前后綴相同的情況
1，初始化
首先我們定義一個(gè)函數(shù) getNext 去構(gòu)建 next 數(shù)組辱挥，函數(shù)參數(shù)為指向 next 數(shù)組的指針犁嗅，和一個(gè)字符串。
void getNext(int* next, string needle) //利用函數(shù)封裝晤碘，使主函數(shù)邏輯更加簡(jiǎn)潔
由于我們要比較一個(gè)字符串的前綴后綴褂微，那就必須有兩個(gè)指針?lè)謩e在字符串的開(kāi)頭和結(jié)尾。而對(duì)于 next 而言园爷，第一位只有一個(gè)字母的情況前綴后綴都是 0 宠蚂，可以直接初始化。
int left = 0;
next[0] = left;
for (int right = 1; right < needle.size(); right++) {
}
2童社，后綴不相同
如果在中間某個(gè)位置發(fā)現(xiàn) right 與 left 的值不相同求厕，就需要不斷進(jìn)行回溯。
由于 next 數(shù)組保留著前后綴相同的位置扰楼，那么回溯的位置便是 next 數(shù)組中 left 的前一個(gè)位置 left - 1 呀癣。如果回溯后的 left 仍然不等于 right 位置的字符，那就繼續(xù)回溯灭抑，直到 left 到達(dá)字符串左邊界十艾。但是為了防止 left - 1 溢出數(shù)組邊界，left = 1 時(shí)便就是邊界了腾节，因此判斷條件為 left > 0忘嫉。
while (left > 0 && needle[left] != needle[right]) {
left = next[left - 1];
}
3，后綴相同
如果 left 和 right 的后綴相同案腺，那么說(shuō)明找到了相同的前后綴庆冕。left，right 遞增劈榨，同時(shí)把 left 的值賦給 next 數(shù)組访递。
if (needle[left] == needle[right]) {
left++;
}
next[right] = left;
4，完整代碼
因此同辣，構(gòu)建 next 數(shù)組完整代碼如下：（時(shí)間復(fù)雜度O(n)）
void getNext(int* next, string needle) {
int left = 0;
next[0] = left;
for (int right = 1; right < needle.size(); right++) {
while (left > 0 && needle[left] != needle[right]) {
left = next[left - 1];
}
if (needle[left] == needle[right]) {
left++;
}
next[right] = left;
}
}
二拷姿、利用 next 數(shù)組進(jìn)行匹配
那么有同學(xué)就要問(wèn)了，得到這個(gè)前綴表旱函，到底對(duì)字符串匹配過(guò)程有什么幫助呢响巢？
別急，我們來(lái)看一個(gè)小例子棒妨。
- 例：如果我們要從 aabaabaafa 中尋找 aabaaf 第一次出現(xiàn)的位置踪古。
1，暴力解法：兩個(gè)字符串均從第一個(gè)位置開(kāi)始比較，比較到第6位發(fā)現(xiàn) b 不等于 f 伏穆，比較失敗拘泞。長(zhǎng)串走到第二個(gè)位置；短串回到第一個(gè)位置枕扫，繼續(xù)比較直到長(zhǎng)串走完陪腌。（ 時(shí)間復(fù)雜度O(m * n））
2，KMP算法：兩個(gè)字符串均從第一個(gè)位置開(kāi)始比較烟瞧，比較到第6位發(fā)現(xiàn) b 不等于 f偷厦，比較失敗。長(zhǎng)串位置不變燕刻；短串，調(diào)用 next 數(shù)組剖笙，找到 next 數(shù)組第5位的數(shù)字卵洗，并作為位置傳遞給短串，這時(shí)候短串到第3位 b 字符弥咪，和長(zhǎng)串匹配过蹂，比較繼續(xù)。（時(shí)間復(fù)雜度O(m)）
匹配錯(cuò)誤時(shí)
只是再解釋一下匹配錯(cuò)誤時(shí)的情況聚至，第6位 f 匹配失敗酷勺，這時(shí)候第5位 next 數(shù)組的值為2，這說(shuō)明此時(shí)第4扳躬、5位和第1脆诉、2位相同，又因?yàn)榈?贷币、5位已經(jīng)和長(zhǎng)串匹配成功击胜，這說(shuō)明第1、2位也可以匹配成功役纹，因此直接從第三位偶摔，也就是數(shù)組下標(biāo)為2的地方開(kāi)始短串匹配即可。
匹配成功時(shí)
長(zhǎng)短串位置均正常遞增即可促脉，只是需要增加結(jié)束條件辰斋，即短串位置到達(dá)短串右端點(diǎn)，這說(shuō)明長(zhǎng)串已經(jīng)有位置可以將短串完全匹配瘸味，循環(huán)結(jié)束宫仗。
我們可以發(fā)現(xiàn)，匹配過(guò)程和 next 數(shù)組生成過(guò)程代碼幾乎完全一樣硫戈，因此代碼的思路模版可以進(jìn)行記憶背誦锰什。
- 完整代碼：
int n = 0;
for (int h = 0; h < haystack.size(); h++) {
while (n > 0 && haystack[h] != needle[n]) {
n = next[n - 1];
}
if (haystack[h] == needle[n]) {
++n;
}
if (n == needle.size()) {
return h - needle.size() + 1;
}
}
return -1;
KMP完整代碼
class Solution {
public:
void getNext(int* next, string needle) {
int left = 0;
next[0] = left;
for (int right = 1; right < needle.size(); right++) {
while (left > 0 && needle[left] != needle[right]) {
left = next[left - 1];
}
if (needle[left] == needle[right]) {
left++;
}
next[right] = left;
}
}
int strStr(string haystack, string needle) {
if (needle.size() == 0) {
return 0;
}
int next[needle.size()];
getNext(next, needle);
int n = 0;
for (int h = 0; h < haystack.size(); h++) {
while (n > 0 && haystack[h] != needle[n]) {
n = next[n - 1];
}
if (haystack[h] == needle[n]) {
++n;
}
if (n == needle.size()) {
return h - needle.size() + 1;
}
}
return -1;
}
};
