前言

• 眾所周知，字符串查找的應(yīng)用范圍非常廣，網(wǎng)頁上有各式各樣的瀏覽器搜索，再到編程需要的vsCode或vsStudio都自帶了搜索功能；一個查找算法的優(yōu)劣可以直接影響用戶的搜索體驗如何
• 但鑒于暴力搜索算法的O(m * n)復(fù)雜度，就有了K姓大佬，M姓大佬，P姓大佬設(shè)計出來的一套O(n + m)字符串查找算法；于是他們的名字被載入史冊，且這套算法被命名為KMP算法
• leetcode指路： 找出字符串中第一個匹配項的下標(biāo)

剛接觸KMP算法時，你大概會覺得這個算法非常詭異，一波詭異的操作處理后生成了一個next數(shù)組，又一波詭異的遍歷操作后，就找到了目標(biāo)位置(？？？WTF)；
代碼倒是不長，每個單詞都認識，但是放一塊就不認識了，像極了四級英語閱讀。。

創(chuàng)新互聯(lián)建站主營金溪網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營網(wǎng)站建設(shè)方案,成都app開發(fā),金溪h5微信小程序搭建,金溪網(wǎng)站營銷推廣歡迎金溪等地區(qū)企業(yè)咨詢一、需要提前明白的概念 1. 大前后綴

首先你需要知道大前后綴是什么；

• 大前后綴就是 在一段字符串中，從首尾分別開始，可能形成的大相等字符子串

以下圖為例：在箭頭位置上，它的前置大前后綴為abb

以下圖為例：在箭頭位置上，它的前置大前后綴為abbsab

看到這里你可能會有疑惑，大前后綴的規(guī)則是什么？下面簡單進行一個總結(jié)：

1. 大前綴 與 大后綴必須相等。
2. 大前后綴必須小于它可取的長度；即：圖一中大前后綴不能同時取abbsabb（s以前的所有字符），圖二中大前后綴不能取b以前的所有字符，那樣的話就失去了它的意義。
3. 大前后綴必須盡可能的長；圖二中可能相等的前后綴有：ab、abbsabb，我們需要取其中較大的那個。

2.next數(shù)組

• next數(shù)組專門用于保存字符串的每個位置之前，它的大前后綴長度
  比如在剛剛的那個字符串所對應(yīng)的next數(shù)組
  

• 再舉一個例子：
  

• 它的每個位置，都記錄著在它位置之前的子串中的大前后綴長度。

至于next數(shù)組是哪里來的，有什么用？會放在后面講。

二、主邏輯 1.主要步驟：

這里先展示一下如何使用大前后綴

• 比如有字符串str1和str2，要求在str1中查找str2位置；（這里的字符串跟上面關(guān)于next講解的部分的沒關(guān)系，千萬不要搞混了）

• 首先假設(shè)我們已經(jīng)得到了str2的正確的next數(shù)組
  那么我們怎么通過已知的信息來對暴力解法進行優(yōu)化呢？

• 經(jīng)過之前7個字符的比較，指針順利來到了s位置
  

• 此時發(fā)現(xiàn)該位置兩個該位置不匹配，那咋辦？

• 此時我們已經(jīng)知道了str2的next數(shù)組中，x位置上的前置子串大前后綴長度為3

• 那這是不是代表，我把str2字符串向前移到相對應(yīng)得位置，那么此時str1和str2得前綴依然是匹配上了：
  

這一步，過濾了暴力解法的主串指針回溯過程
那么為什么可以這么跳過呢？
主要分兩個證明：

1. 前后綴相等，則字符串跳轉(zhuǎn)后，下標(biāo)位置處 前字串也一定匹配
2. 跳轉(zhuǎn)經(jīng)過的區(qū)間內(nèi)，一定不存在與主串匹配的存在

問題一自不用說，肉眼可見，下面主要證明步驟2；為什么經(jīng)過區(qū)間一定不含可能匹配的存在

• 假設(shè)：如果在經(jīng)過區(qū)間上存在可匹配的存在，那么將說明此時該區(qū)間內(nèi)存在更大的前后綴，這與next數(shù)組中的已求得數(shù)據(jù)不符，所以該結(jié)論不成立。
  

2.跳躍方式

• 跳躍到哪個位置將由next數(shù)組決定，next數(shù)組與str2共用一個下標(biāo)，需要查詢前綴位置直接在next的對應(yīng)下標(biāo)位置尋找

• 例如下圖中，在箭頭位置 首次匹配失敗，通過直接查詢next數(shù)組中x的對應(yīng)位置找到需要跳轉(zhuǎn)的下標(biāo)。
  

• 這里還匹配失敗如下圖：
  

• 那么這里就再次進行跳轉(zhuǎn)，跳轉(zhuǎn)到0位置繼續(xù)匹配
  

• 如果str2指針已經(jīng)跳到0位置，還匹配失敗的話，就挪動主串指針：
  

以上就是主串的整個匹配過程。
計算可得：這個過程的大時間復(fù)雜度不超過O(2 * N)

3.主要代碼

int strStr(string str1, string str2) {vectornext;
        func(next, str2);					//求next數(shù)組

        int idx1 = 0;
        int idx2 = 0;
        while(idx1< str1.size())
        {if(str1[idx1] == str2[idx2])	//匹配上就兩個指針一起往下走
            {idx1++;
                idx2++;
                if(idx2 == str2.size())
                {return idx1 - idx2;
                }
            }
            else if(idx2 == 0)				//沒匹配上而且idx2在0位置
            {idx1++;
            }
            else{	//沒匹配上  idx2不在0位置
                idx2 = next[idx2];
            }
        }
        return -1;
    }

三、求next數(shù)組

• 求next數(shù)組所用的是經(jīng)典的動態(tài)規(guī)劃過程，簡單來說就是兩個指針一個在頭部找前綴，一個指針在尾部找后綴。
• 這里不能使用暴力求解的方法，因為暴力求解的最高時間復(fù)雜度為O(m ** 2)，那么在某些極端情況下，整個算法的時間復(fù)雜度會漲到O(n ** 2)

1.總過程

我不論如何，先給next數(shù)組填一個0

• 為啥這么做呢？是因為下標(biāo)0位置不包含前綴，而且這一位也不會被訪問到，我們真正開始計算next數(shù)組是從1號下標(biāo)開始。

• 創(chuàng)建兩個指針，分別尋找前綴和后綴，這里用顏色區(qū)分。
  

• 第一步發(fā)現(xiàn)：兩個字符相等，那么都自增，后綴位置next數(shù)組內(nèi)填(前綴指針下標(biāo) + 1)即(0 + 1)
  

• 第二步發(fā)現(xiàn)：還相等，重復(fù)上過程
  

• 第三步發(fā)現(xiàn)：她兩不相等，那么就通過已知大前綴數(shù)來找到需要跳轉(zhuǎn)到的位置：next[1]== 1
  

• 第四步發(fā)現(xiàn)：她兩還不相等，那么通過已知大前綴數(shù)來找到需要跳轉(zhuǎn)到的位置：next[0] == 0
  

• 此時發(fā)現(xiàn)她兩還不相等，但是 前綴下標(biāo)已經(jīng)走到了0位置， 所以說明s位置不存在任何可以匹配的相等前后綴，就給該位置賦0然后后綴指針自增

繼續(xù)重復(fù)上述過程：



以上就是整個next數(shù)組的求解過程，主要采用動態(tài)規(guī)劃的形式，以類似主邏輯的方式將整個next數(shù)組求解。

• 注：實際上next數(shù)組的最前一位和最后一位都用不到，邏輯上next數(shù)組第0位必須存在，最后一位可以不存在

四、代碼

class Solution {//求next 數(shù)組
    void func(vector& next, string& str2)
    {next.resize(0);
        next.push_back(0);
        int idx1 = 1;
        int idx2 = 0;
        while(idx1< str2.size())
        {//相等則next填充，兩指針自增
            if(str2[idx1] == str2[idx2])
            {next.push_back(++idx2);
                idx1++;
            }//格式串在最左部，
            else if(idx2 == 0)
            {next.push_back(0);
                idx1++;
            }
            else{//可以向前找
                idx2 = next[idx2 - 1];
            }
        }
    }
public:
	int strStr(string str1, string str2) {vectornext;
        func(next, str2);					//求next數(shù)組

        int idx1 = 0;
        int idx2 = 0;
        while(idx1< str1.size())
        {if(str1[idx1] == str2[idx2])	//匹配上就兩個指針一起往下走
            {idx1++;
                idx2++;
                if(idx2 == str2.size())
                {return idx1 - idx2;
                }
            }
            else if(idx2 == 0)				//沒匹配上而且idx2在0位置
            {idx1++;
            }
            else{	//沒匹配上  idx2不在0位置
                idx2 = next[idx2];
            }
        }
        return -1;
    }
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站名稱：C++實現(xiàn)字符串查找KMP算法-創(chuàng)新互聯(lián)
當(dāng)前URL：http://chinadenli.net/article20/cdoojo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供服務(wù)器托管、網(wǎng)站設(shè)計、動態(tài)網(wǎng)站、ChatGPT、軟件開發(fā)、營銷型網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)