學(xué)習(xí)筆記三 KMP算法介紹

本題來自：力扣28.實(shí)現(xiàn)strStr()

題目描述

簡單來說，題目要求是從一個字符串 haystack 中找到另一個字符串 needle 出現(xiàn)的第一個位置。如果按暴力解法，題目解答很容易想到是 O(m * n) 的時間復(fù)雜度。那么，有沒有一種解法，它的時間復(fù)雜度可以降到 O(m + n) 呢？

有！這就是我們接下來要介紹的 KMP 算法

KMP的主要思想

• KMP的主要思想是：當(dāng)出現(xiàn)字符串不匹配時，可以知道一部分之前已經(jīng)匹配的文本內(nèi)容，避免從頭再去做匹配了。這也是我們能將時間復(fù)雜度降低的本質(zhì)。

KMP實(shí)現(xiàn)的關(guān)鍵步驟

一、構(gòu)建 next 數(shù)組

先來解釋幾個名詞：前綴，后綴，最長公共前后綴，前綴表

前綴：不包含最后一個字符的，并以第一個字符為開頭的所有子字符串
后綴：不包含第一個字符的，并以最后一個字符為結(jié)尾的所有子字符串

最長公共前后綴：對于一個字符而言，最長的相同的前綴后綴
前綴表：前綴表是記錄下標(biāo) i 之前（包括 i）的字符串中，有多大長度的最長公共前后綴

而我們要構(gòu)建的 next 數(shù)組，就是所謂的前綴表。

KMP 算法實(shí)現(xiàn)的第一個難點(diǎn)便是 next 數(shù)組的構(gòu)建求解，即 對于一個子串，如何去求它的最長公共前后綴？

構(gòu)造 next 數(shù)組其實(shí)就是計(jì)算短串的前綴表的過程，其關(guān)鍵步驟主要有如下三步：

• 初始化
• 處理前后綴不相同的情況
• 處理前后綴相同的情況

1，初始化

首先我們定義一個函數(shù) getNext 去構(gòu)建 next 數(shù)組，函數(shù)參數(shù)為指向 next 數(shù)組的指針，和一個字符串。

void getNext(int* next, string needle)   //利用函數(shù)封裝，使主函數(shù)邏輯更加簡潔

由于我們要比較一個字符串的前綴后綴，那就必須有兩個指針分別在字符串的開頭和結(jié)尾。而對于 next 而言，第一位只有一個字母的情況前綴后綴都是 0 ，可以直接初始化。

int left = 0;
next[0] = left;
for (int right = 1; right < needle.size(); right++) {
        
}

2，后綴不相同

如果在中間某個位置發(fā)現(xiàn) right 與 left 的值不相同，就需要不斷進(jìn)行回溯。

由于 next 數(shù)組保留著前后綴相同的位置，那么回溯的位置便是 next 數(shù)組中 left 的前一個位置 left - 1 。如果回溯后的 left 仍然不等于 right 位置的字符，那就繼續(xù)回溯，直到 left 到達(dá)字符串左邊界。但是為了防止 left - 1 溢出數(shù)組邊界，left = 1 時便就是邊界了，因此判斷條件為 left > 0。

while (left > 0 && needle[left] != needle[right]) {
    left = next[left - 1];
}

3，后綴相同

如果 left 和 right 的后綴相同，那么說明找到了相同的前后綴。left，right 遞增，同時把 left 的值賦給 next 數(shù)組。

if (needle[left] == needle[right]) {
    left++;
}
next[right] = left;

4，完整代碼

因此，構(gòu)建 next 數(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é)就要問了，得到這個前綴表，到底對字符串匹配過程有什么幫助呢？
別急，我們來看一個小例子。

• 例：如果我們要從 aabaabaafa 中尋找 aabaaf 第一次出現(xiàn)的位置。

1，暴力解法：兩個字符串均從第一個位置開始比較，比較到第6位發(fā)現(xiàn) b 不等于 f ，比較失敗。長串走到第二個位置；短串回到第一個位置，繼續(xù)比較直到長串走完。（ 時間復(fù)雜度O(m * n））
2，KMP算法：兩個字符串均從第一個位置開始比較，比較到第6位發(fā)現(xiàn) b 不等于 f，比較失敗。長串位置不變；短串，調(diào)用 next 數(shù)組，找到 next 數(shù)組第5位的數(shù)字，并作為位置傳遞給短串，這時候短串到第3位 b 字符，和長串匹配，比較繼續(xù)。（時間復(fù)雜度O(m)）

匹配錯誤時

只是再解釋一下匹配錯誤時的情況，第6位 f 匹配失敗，這時候第5位 next 數(shù)組的值為2，這說明此時第4、5位和第1、2位相同，又因?yàn)榈?、5位已經(jīng)和長串匹配成功，這說明第1、2位也可以匹配成功，因此直接從第三位，也就是數(shù)組下標(biāo)為2的地方開始短串匹配即可。

匹配成功時

長短串位置均正常遞增即可，只是需要增加結(jié)束條件，即短串位置到達(dá)短串右端點(diǎn)，這說明長串已經(jīng)有位置可以將短串完全匹配，循環(huán)結(jié)束。

我們可以發(fā)現(xiàn)，匹配過程和 next 數(shù)組生成過程代碼幾乎完全一樣，因此代碼的思路模版可以進(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;
    }
};