目錄

?前言：

?KMP算法簡(jiǎn)介：

引入概念：

前綴后綴

前綴表：

簡(jiǎn)單例子：

暴力遍歷：

KMP算法：?

?KMP算法難點(diǎn)：

總結(jié)：

?前言：

本篇我們將詳細(xì)的從理論層面介紹一下什么是KMP算法，相對(duì)應(yīng)的力扣刷題專欄里也會(huì)有相對(duì)應(yīng)的習(xí)題，歡迎各位前往閱讀。

?KMP算法簡(jiǎn)介：

? ? ? ? ?KMP算法是一種字符串匹配算法，用于在一個(gè)文本串中查找某個(gè)子串出現(xiàn)的位置。KMP算法的原理是根據(jù)模式串的特點(diǎn)，在匹配過程中避免重復(fù)匹配已經(jīng)匹配過的部分。具體來說，KMP算法維護(hù)兩個(gè)指針：i和j，表示當(dāng)前匹配位置和模式串匹配的起點(diǎn)。當(dāng)出現(xiàn)不匹配時(shí)，通過已匹配部分構(gòu)建一個(gè)next數(shù)組，用以確定模式串下一次匹配起點(diǎn)的位置。

? ? ? ? KMP算法的時(shí)間復(fù)雜度為O(n+m)，其中n為文本串長(zhǎng)度，m為模式串長(zhǎng)度。KMP算法應(yīng)用廣泛，例如在文件查找、模糊查詢等領(lǐng)域都有廣泛的應(yīng)用。

KMP算法的本質(zhì)就是跳過一部分暴力循環(huán)下的無效比較，達(dá)到節(jié)省時(shí)間復(fù)雜度的目的

引入概念：

前綴后綴

前綴：字符串中包含首字母但是不包含尾字符的所有子串

后綴：字符串中包含尾字母但是不包含首字符的所有子串

舉例：

字符串aabaaf的前綴后綴分別有：

前綴表：

一個(gè)字符串中每一個(gè)子串都有自己的前綴和后綴，也就都有自己的最長(zhǎng)相等前后綴長(zhǎng)度，這些長(zhǎng)度組成的一個(gè)數(shù)組，我們把它叫做前綴表

舉例：
字符串aabaaf的前綴表：

簡(jiǎn)單例子：

假設(shè)我們要在父串aabaabaaf中尋找子串aabaaf

暴力遍歷：

正常情況是我們?cè)诟复兄鹨槐闅v，父串與子串挨個(gè)匹配，直到找到與子串完全一致的為止：
?

錯(cuò)誤之后重新比較：
?

?最終：

我們可以發(fā)現(xiàn)暴力遍歷之所以時(shí)間復(fù)雜度高，是因?yàn)橹灰鲥e(cuò)，父指針與子指針就會(huì)不斷的回溯。第一次出錯(cuò)后，父類指針回溯到1，子類指針回溯到0，重新開始比較，第二次出錯(cuò)父類指針回溯到2，子類指針回溯到0，重新開始比較。如此類推。大量的回溯帶來了高昂的時(shí)間成本，我們就在想如何才能夠精簡(jiǎn)回溯，于是經(jīng)過不懈努力，我們創(chuàng)造出了KPM算法。

? ?KMP算法：

KMP算法采取了自定義i和j的回溯，通過控制i和j的回溯位置來降低回溯的時(shí)間成本。

?此時(shí)按照暴力遍歷的思路，我們是讓i等于1，j等于0重新開始第二輪遍歷，但是我們KMP算法給出了新的思路：

我們不對(duì)已經(jīng)比較過的字符串進(jìn)行二次比較，就節(jié)省了回溯成本，既然綠色前綴和紅色后綴相等，都是aa，那么下一次我們讓子類的綠色前綴對(duì)齊父類的紅色后綴，這樣我們就不用回溯i和j，也可以開啟新一輪的字符串對(duì)比

為什么可以這樣操作呢？

前提是我們已經(jīng)知道前面字符串只有b和f不匹配，其他的一切都是匹配的，那么此時(shí)往前回溯字符串

?找到兩串最長(zhǎng)的相等的一個(gè)包含首字母的字符串（前綴），一個(gè)包含尾字母的字符串（后綴），因?yàn)槎呤窍嗟鹊模敲次覀兙涂梢缘玫紸BCD四個(gè)子串：

那其實(shí)我們這里不移動(dòng)最長(zhǎng)的也可以，只不過移動(dòng)最長(zhǎng)的會(huì)簡(jiǎn)化的更多而已。

那么既然B和D匹配，D又和C匹配，也就是我們?cè)谙乱淮窝h(huán)的時(shí)候，可以直接讓B對(duì)齊C，而BC又是匹配的，我們不用重新對(duì)其進(jìn)行匹配，可以直接從此處的i和j開始。

?而不斷的循環(huán)這種比較方法，直至找到父類中符合要求的子串，就實(shí)現(xiàn)了KMP算法下的字符串匹配。

?

通過這個(gè)我們可以總結(jié)出來模板：

? ? ? ? 每一次我們都找到不匹配字母前面的字符串（例如我們這里aabaaf中f不匹配，前置字符串就是aabaa）然后找出他的最長(zhǎng)相等前綴后綴長(zhǎng)度（找出有無符合上述這種紅綠組合的），這里的最長(zhǎng)相等前綴后綴是2，最后我們讓i不回溯，j回退到最長(zhǎng)相等前綴后綴位置開始向后匹配。

? ? 而next數(shù)組其實(shí)就是我們?yōu)榱朔奖闶褂貌黄ヅ渥帜盖爸玫淖址淖铋L(zhǎng)相等前綴后綴長(zhǎng)度，我們自己進(jìn)行提前算出這個(gè)字符串的所有子串的最長(zhǎng)相等前綴后綴長(zhǎng)度，存儲(chǔ)在一個(gè)數(shù)組里面方便直接使用，我們給這個(gè)把這個(gè)數(shù)組叫做next數(shù)組

? ? ?需要注意的是next數(shù)組的版本多種多樣，通常會(huì)對(duì)里面的數(shù)據(jù)進(jìn)行各種處理。不過本質(zhì)存放的都是前綴表，因此我們其實(shí)可以不對(duì)next數(shù)組做任何處理，就讓他存放前綴表，依然可以實(shí)現(xiàn)KMP算法。

以下這句話，對(duì)于理解為什么使用前綴表可以告訴我們匹配失敗之后跳到哪里重新匹配 非常重要！

下標(biāo)5之前這部分的字符串（也就是字符串a(chǎn)abaa）的最長(zhǎng)相等的前綴 和 后綴字符串是 子字符串a(chǎn)a ，因?yàn)檎业搅俗铋L(zhǎng)相等的前綴和后綴，匹配失敗的位置是后綴子串的后面，那么我們找到與其相同的前綴的后面從新匹配就可以了。

所以前綴表具有告訴我們當(dāng)前位置匹配失敗，跳到之前已經(jīng)匹配過的地方的能力。

next表的種類：

我們還是以aabaaf舉例：

?KMP算法難點(diǎn)：

整個(gè)KMP算法都可以看作兩部分

• 內(nèi)核：前綴表的求解，建立next數(shù)組
• 外殼：利用前綴表控制子字符串的回溯

主要的難點(diǎn)在于：如何求字符串的前綴表?

其實(shí)字符串的前綴表數(shù)組計(jì)算本質(zhì)上也是在運(yùn)用KMP算法。

它是把字符串的前綴當(dāng)作了模式串，把字符的后綴當(dāng)成了文本串

void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) { // j要保證大于0，因?yàn)橄旅嬗腥-1作為數(shù)組下標(biāo)的操作
                j = next[j - 1]; // 注意這里，是要找前一位的對(duì)應(yīng)的回退位置了
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }

KMP算法完整版：

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

總結(jié)：

KMP算法的優(yōu)點(diǎn)主要包括以下幾點(diǎn)：

1. 高效率：KMP算法的時(shí)間復(fù)雜度為O(n+m)，其中n是文本串長(zhǎng)度，m是模式串長(zhǎng)度，相比暴力匹配算法的時(shí)間復(fù)雜度O(nm)有很大的提升。

2. 可擴(kuò)展性：KMP算法不要求文本和模式串的長(zhǎng)度一致，因此能夠有效地處理不同長(zhǎng)度的字符串匹配問題。此外，KMP算法還可以支持多模式匹配，即在一個(gè)文本串中查找多個(gè)模式串。

3. 避免重復(fù)匹配：KMP算法通過計(jì)算模式串的next數(shù)組來避免重復(fù)匹配已經(jīng)匹配過的部分，從而提高了匹配效率。

4. 空間復(fù)雜度低：KMP算法只需要一個(gè)長(zhǎng)度為m的next數(shù)組來存儲(chǔ)模式串中最長(zhǎng)相同前后綴的長(zhǎng)度，空間復(fù)雜度相對(duì)較低。

5. 實(shí)現(xiàn)簡(jiǎn)單：KMP算法的實(shí)現(xiàn)相對(duì)簡(jiǎn)單，易于理解和使用。

總之，KMP算法是一種高效、可擴(kuò)展、避免重復(fù)匹配、空間復(fù)雜度低、實(shí)現(xiàn)簡(jiǎn)單的字符串匹配算法，對(duì)于字符串匹配問題具有廣泛的應(yīng)用價(jià)值。

今天的內(nèi)容到這里就結(jié)束了，感謝大家的閱讀。

如果我的內(nèi)容對(duì)你有幫助，請(qǐng)點(diǎn)贊，評(píng)論，收藏。創(chuàng)作不易，大家的支持就是我堅(jiān)持下去的動(dòng)力！

?文章來源地址http://www.zghlxwxcb.cn/news/detail-479713.html

到了這里，關(guān)于【夜深人靜學(xué)數(shù)據(jù)結(jié)構(gòu)與算法 | 第一篇】KMP算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！