KMP算法

看到這么一句話(huà)：你的名字是我告白語(yǔ)中的子串

文章目錄

• • KMP算法
  • • 參考代碼
    • 預(yù)處理模式串的理解
    • 入門(mén)題目

KMP一開(kāi)始理解起來(lái)是比較困難的，下方是結(jié)合自己的理解寫(xiě)出來(lái)代碼，僅作參考，

（網(wǎng)上大部分人處理next數(shù)組時(shí)，對(duì)next數(shù)組整體移動(dòng)了一格。但是我覺(jué)得不是特別好理解，所以我寫(xiě)的代碼next數(shù)組并沒(méi)有作移動(dòng)）部分解釋請(qǐng)參考注釋。

參考代碼

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e5+5; int next[N]; void getNext(const char *s,int *next) {/** description:* 構(gòu)建模式串的前后綴相等的最大長(zhǎng)度* next[i]:存儲(chǔ)串s[0...i]前后綴相等的最大長(zhǎng)度* 特別考慮s[i] != s[j]:* 現(xiàn)在前后綴不相等，i不移動(dòng)(除非j回退到0)，* j需要回退，即縮小前后綴，但是要縮的盡可能小，* 由特殊的“對(duì)稱(chēng)性”，j應(yīng)該回退到 next[j-1]* return: */int len = strlen(s);int i = 1,j = 0;next[0] = 0;while(i < len){if(s[i] == s[j]){next[i++] = ++j;}else{j > 0 ? j=next[j-1] : next[i++]=0;}} } int KMP(const char *t,const char *s) {/** description: t串中找子串s* return: 匹配的第一個(gè)子串的首位置（index）*/int i,j;i = j = 0;int lent = strlen(t);int lens = strlen(s);while(i < lent){if(t[i] == s[j]){++i;++j;}else{j > 0 ? j=next[j-1] : i++;}if(j == lens) //如需匹配多個(gè),虛擬模式串s[j]有元素（此時(shí)肯定失配）：j = next[j-1]break;}return j == lens ? (i-lens): -1; } int main() {const char *t = "aabcaabaabaaad";const char *s = "aabaabaaa";getNext(s,next);int first_pos = KMP(t,s);cout<<first_pos<<endl;return 0; }

預(yù)處理模式串的理解

用兩個(gè)“指針”：i, j （i在后，j在前）
next[i]:存儲(chǔ)串s[0…i]前后綴相等的最大長(zhǎng)度，

• 前綴：去掉最后一個(gè)字符，以第一個(gè)字符開(kāi)始的字符串；
• 后綴，去掉第一個(gè)字符，以最后一個(gè)字符結(jié)尾的字符串；
  比如：application,s[0…4]前綴：a,ap,app,appl,后綴：ppli,pli,li,i

初始化：next[0] = 0, i = 1,j = 0
考慮的兩種情況：

• s[i] == s[j]: 兩個(gè)指針均移動(dòng)（i++，j++）
• s[i] != s[j]: j需要回退盡可能少，j回退到next[j-1],
  需要防止j-1數(shù)組越界，當(dāng)j==0時(shí)，即此時(shí)j已經(jīng)無(wú)法回退了，只有移動(dòng)i才可能產(chǎn)生匹配的前后綴。
  (這里堪稱(chēng)KMP算法最難理解的地方)理解不了可以看下圖：

入門(mén)題目

洛谷：P3375 【模板】KMP字符串匹
AC代碼：

#include <iostream> #include <string>using namespace std; const int N = 1e6+5; int pNext[N]; void getNext(string p,int len) {int j,i;i = 1,j = 0;while(i < len){if(p[i] == p[j]){pNext[i] = ++j;i++;}else{if(j > 0)j = pNext[j-1];elsepNext[i++] = 0;}} } void KMP(string s,string p,int lenp) {int i,j;i = j = 0;int lens = s.length();while(i < lens){if(s[i] == p[j]){i++;j++;}else{if(j > 0) j = pNext[j-1];else i++;}if(j == lenp){int pos = i - lenp + 1;/** 匹配成功后繼續(xù)匹配：* j從0開(kāi)始的，j==lenp時(shí)，* j已經(jīng)超出模式串p的范圍，* 虛擬模式串s[j]有元素，此時(shí)肯定失配，則：j = next[j-1]*/j = pNext[j-1]; cout<<pos<<endl;}} } int main() {string s,p;cin>>s>>p;int lenp = p.length();getNext(p,lenp);KMP(s,p,lenp);cout<<pNext[0];for(int i = 1; i < lenp; ++i){cout<<" "<<pNext[i];}cout<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的深化对KMP算法的理解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。