KMP算法核心思想
利用已經(jīng)匹配的數(shù)據(jù),去除無效的從頭匹配
KMP算法流程
首先我們找到 i=9,j=9時不匹配,如果時暴力算法,此時i應(yīng)重新來到i=2的位置,j返回j=1的位置,開始新一輪的匹配
這樣暴力匹配,就白白浪費(fèi)了已經(jīng)匹配的串,那么問題來了,我們應(yīng)該如何利用已經(jīng)匹配的串呢??
我們看著圖片,假設(shè)i返回i=2,j返回j=1,i++,j++,i指向b,j指向a,此時就不匹配了,又要重新開始,i來到3,j又回到j(luò)=1,雙方指向第一個元素就不匹配,kmp算法的核心就是過濾掉這種低效的匹配,我們往下看
我們直到i=9和j=9前面的串 a a b a a b a a無論在S串或者J串是完全相等的,這也就意味著,我下面的操作無論在S串操作或者在J串操作,只要不出這個范圍,在哪里操作都是一樣的,因?yàn)樗麄兌际峭淮?
我們找到緊挨著i=9,元素b前的一串后綴(aabaa),一定要緊挨著,然后找到 J串從第一個元素開始的,與aabaa相等的前綴! 為什么要這樣找呢?? 我們可以發(fā)現(xiàn)i從這個前綴的第一個元素開始能夠完全匹配,J從第一個元素開始一直到這個綴結(jié)束,這樣就可以過濾掉,大量的無效匹配,比如剛才的 i=2,i=3,都屬于無效匹配
此時有個疑問,既然是緊挨著i=9的后綴,和J第一個元素出發(fā)的前綴,那么aa不可以嗎?? 當(dāng)然可以啦,從aa開始匹配,也就是i=7開始,新一輪匹配,但是這樣會丟解,也就是,i跳的步子大了,跨過了可行解的下標(biāo)!
通過上面的鋪墊,我們引出一個概念
最長相等前后綴
從第一個元素開始,不包括最后一個元素結(jié)束,和從最后一個元素開始,不包括第一元素得出的前綴和后綴,前綴和后綴滿足,相等且最長
通過上面講解,我們就是要利用這個最長相等前后綴,達(dá)到過濾無效匹配的效果,上面講過,我的操作完全可以只在J串進(jìn)行,無需在S串進(jìn)行,所以我讓i=9不動,讓J移動到J=5的位置,開始匹配i,和j+1所對應(yīng)元素是否相等即可! 這也就相當(dāng)于暴力算法,從i=4開始匹配,匹配到了i=8的位置,故通過尋找最長相等前后綴可以快速達(dá)到此效果!!
故:在使用kmp算法時,需要求出J串的每個位置的最長相等前后綴 (有的算法實(shí)現(xiàn)時會求出,每個位置 ‘前’ 的最長相等前后綴,這在后面會講解,不同的求法,實(shí)現(xiàn)代碼不同,因此會有差異)
求解Next數(shù)組
我們依J串為例a a b a a b a a a a求出它的Next數(shù)組(next數(shù)組存放每個位置的最長前后綴)
那么如何用代碼實(shí)現(xiàn)呢?
我們先觀察next數(shù)組,我們發(fā)現(xiàn)只要多進(jìn)來一個元素,并且滿足最長前后綴,那么next數(shù)組就會增加1,那么如果不滿足呢? 實(shí)際上我們觀察代碼可看到i起始從2開始,j從0開始,每次用j+1的位置進(jìn)行匹配,我們可以理解為雖然用的是同一條串,但是由于i和j從不同起點(diǎn)出發(fā)導(dǎo)致,出現(xiàn)了一個新兩個串匹配問題,那么就可以轉(zhuǎn)化為我們剛剛講的kmp思想
我們看以下匹配模擬過程
當(dāng)i=9時,j=5,j+1元素為b與a并不匹配,也就意味著i=9無法繼續(xù)發(fā)揚(yáng)光大,無法繼承上依次最大前后綴,所以需要尋找新的,也就回到了最初的兩個串匹配問題,不同則回退,所以j回退到next[5]的位置(此時next[5]已經(jīng)求出來了),j落到j(luò)=2,用j+1繼續(xù)匹配i,發(fā)現(xiàn)匹配仍然失敗b!=a,故j移動到next[j]位置也就是j=1,繼續(xù)用j+1匹配,匹配成功,退出while循環(huán),i++,j++,接著算出next[10]
這里解釋以下為什么j從0開始,i從2開始,如果j從0開始,i從2開始,那么每次只需要用j+1去匹配i(“進(jìn)可攻”),如果不匹配直接j=next[j] (“退可守”),所以我們現(xiàn)在的next數(shù)組含義是如果正在匹配的元素不相等,則需要他們之前的next[j],而不是他們自身的next[j],后面會講解,直接利用自身的next不必需要前一個位置的next回退(一定注意區(qū)分)
模式串與主串匹配過程
這里的代碼和求next函數(shù)代碼十分相似,只是求next函數(shù)用的一個串,這里變?yōu)榱藘蓚€串,注意起始位置,i從1開始j從0開始,之前是i從2開始,因?yàn)橹挥袕?開始才能領(lǐng)先一個位置,用j+1去比較,不然j+1和i指向同一個元素?zé)o法達(dá)到進(jìn)可攻退可守的效果!
競賽版本代碼
kmp模板題目洛谷P3375
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int ne[maxn];
int la,lb; //主串長la,子串長lb
char a[maxn],b[maxn]; //a主串 b子串
int main()
{
cin>>a+1;
cin>>b+1;
la=strlen(a+1);
lb=strlen(b+1);
//預(yù)處理next函數(shù)
for(int i=2,j=0;i<=lb;i++)
{
while(j&&b[i]!=b[j+1])j=ne[j]; //如果不匹配每次向前跳
if(b[i]==b[j+1])j++;//匹配則j指針前移
ne[i]=j;
}
//根據(jù)next數(shù)組進(jìn)行匹配
for(int i=1,j=0;i<=la;i++)
{
while(j&&a[i]!=b[j+1])j=ne[j];//模式串前移動,也就是回跳
if(a[i]==b[j+1])j++;
if(j==lb)printf("%d\n",i-lb+1);
}
for(int i=1;i<=lb;i++)
{
cout<<ne[i]<<" ";
}
return 0;
}
上面版本代碼復(fù)雜,由于求next數(shù)組,遍歷第一個for循環(huán),里面還有while循環(huán),并且i和j的起始位置,也不大相同,但是next數(shù)組的想法特別簡單,就是求解到當(dāng)前位置的,最長前后綴,我么針對next數(shù)組進(jìn)行動手腳,進(jìn)而簡化代碼,下面的代碼也是考研常見的版本,競賽中幾乎不會使用這個版本,兩個版本各有千秋!
對next數(shù)組修改
上面版本每次匹配都需要用j+1的位置去匹配,而非j自身,如果j+1不匹配j進(jìn)行回退,那么反過來一想,能不能讓j自身去匹配,如果不相等,則仍然是執(zhí)行j=next[j]呢? (回退后仍然是j直接匹配)
答案是可以的!
我么將next數(shù)組元素值進(jìn)行向右移動一位,然后+=1就可以達(dá)到此效果!
我們來手動解釋以下,當(dāng)向右移動一位后,next[j]的值表示,前一位的最長相等前后綴,我們此時移動到該位置發(fā)現(xiàn)需要用j+1去和i匹配,所以j還需要+=1,才能直接達(dá)到移動后直接和i去匹配的效果! (時刻記得和之前next數(shù)組的區(qū)別)
前面的next數(shù)組手推,是以當(dāng)前元素為最后一個結(jié)點(diǎn)的最長前后綴,現(xiàn)在的next數(shù)組,需要考慮以前一個元素為結(jié)尾的最長前后綴長度然后在+=1即可,我們來手推以下!
手動匹配next數(shù)組方法
在當(dāng)前元素,前畫一個括弧,尋找括弧中最長前后綴,最后+=1
考研求解next數(shù)組代碼
void get_next(String T,int next[])
{
int i=1,j=0; //i領(lǐng)先一個位置
next[1]=0;
while(i<T.length)
{
if(j==0||T.ch[i]==T.ch[j]) //如果j=0時,意味著當(dāng)前i無法和模式串匹配,i需要向后移動
{
i++;j++; //i++相當(dāng)于next[j]賦值給next[j+1],j++相當(dāng)于移動到可以直接匹配的位置
next[i]=j;
}else{
j=next[j]; //回退
}
}
}
這兩個版本的代碼差異挺大,主要是由于,next數(shù)組右移動一位,然后+=1造成的。初始時i=1,j=0,這樣構(gòu)成字符差,將一串字符劃分為兩串,然后while循環(huán)結(jié)束條件為i<T.length,由于最后一個位置的next[j]由next[j-1]向右移動,所以不需要遍歷到i=T.length
if中的條件中j==0時,由于i和j一直不匹配導(dǎo)致,j=next[j]一直進(jìn)行,所以最后移動到j(luò)=0,即i元素對應(yīng)的子串,沒有最長前后綴,所以需要next[i+1]應(yīng)該跳到1號位置,注意:每次都是求前一個元素的最長前后綴,在賦值給當(dāng)前元素,在代碼中體現(xiàn)就是,滿足if語句,然后i++,這個i++就是手動求next數(shù)組,向右移動一位,然后j++,對應(yīng)如果發(fā)生回跳,應(yīng)該跳到能夠直接去匹配的位置,而不是最長前后綴的最后一位。
if語句中T.ch[i]==T.ch[j],注意此時i宏觀上是i-1,也就是以前一個結(jié)點(diǎn)為最后結(jié)點(diǎn)的最長前后綴,需要注意next[i-1] 并不代表以i-1為最后一個結(jié)點(diǎn)的最長前后綴,所以第i-1對應(yīng)元素作為需要和j匹配的元素,代碼視覺上是i去匹配,實(shí)際上是i-1去匹配,如果匹配成功證明 i-1可以發(fā)揚(yáng)光大,不過匹配失敗,那么最長前后綴只好縮短!
來看下面圖解
如果匹配不成功
考研版本代碼
#include <bits/stdc++.h>
using namespace std;
#define MAXLEN 225
typedef struct
{
char ch[MAXLEN];
int length;
} String;
void get_next(String T,int next[])
{
int i=1,j=0; //i領(lǐng)先一個位置
next[1]=0;
while(i<T.length)
{
if(j==0||T.ch[i]==T.ch[j]) //如果j=0時,意味著當(dāng)前i無法和模式串匹配,i需要向后移動
{
i++;
j++; //i++相當(dāng)于next[j]賦值給next[j+1],j++相當(dāng)于移動到可以直接匹配的位置
next[i]=j;
}
else
{
j=next[j]; //回退
}
}
}
int Index_KMP(String S,String T,int next[])
{
int i=1,j=1;
while(i<=S.length&&j<=T.length)
{
if(j==0||S.ch[i]==T.ch[j])
{
i++,j++;//匹配成功,i和j向后移動
}
else
{
j=next[j];//j回調(diào)可以直接匹配的位置
}
}
if(j>T.length) return i-T.length; //不需要+1,因?yàn)閣hile1循環(huán)退出之前i++,用來while循環(huán)判斷了
else return 0;
}
int main()
{
String s1,s2; //s1母串,s2子串
char a[MAXLEN],b[MAXLEN];
cout<<"輸入母串:"<<endl; //aabaabaabaabaabaaaa
cin>>s1.ch+1;
s1.length=strlen(s1.ch)-1;
cout<<"輸入子串:"<<endl;//aabaabaaaa
cin>>s2.ch+1;
s2.length=strlen(s2.ch)-1;
int next[MAXLEN];
get_next(s2,next);
cout<<"next數(shù)組如下"<<endl;
for(int i=1;i<=s2.length;i++)
{
cout<<next[i]<<" ";
}
cout<<endl;
printf("匹配位置:%d\n",Index_KMP(s1,s2,next));
return 0;
}
運(yùn)行結(jié)果
對KMP算法求解next數(shù)組優(yōu)化(nextval)
由考研版本可知,next數(shù)組是回跳到可以直接匹配的位置,那么問題來了,當(dāng)前i和j所對應(yīng)元素發(fā)生不匹配,j進(jìn)行回跳,如果回跳后的元素和回跳前的元素相當(dāng),那么豈不是白跳了,跳了也是不匹配!
我們看到i=4,j=4發(fā)生不匹配,子串前4個元素相同,那么按照之前的回跳方法需要先跳到j(luò)=3,仍然不匹配,在跳j=2,j=1,j=0,最后i++,元素b匹配失敗,這樣需要回跳好多步,導(dǎo)致性能退化。
解決方法很簡單,只需要在求next數(shù)組過程中,判斷以下當(dāng)前元素和回跳后的元素是否相等即可,如果不相等,則next[i]=j,如果相等,則next[i]=next[j]即可有點(diǎn)遞歸感覺,只需要一次就可以,因?yàn)槭菑那跋蚝笳?所以前面的next[j]一定保證了不會跳到相同元素對應(yīng)位置!
(有動態(tài)規(guī)劃的感覺了)
實(shí)現(xiàn)優(yōu)化next數(shù)組代碼
#include <bits/stdc++.h>
using namespace std;
#define MAXLEN 225
typedef struct
{
char ch[MAXLEN];
int length;
} String;
int Index_KMP(String S,String T,int next[])
{
int i=1,j=1;
while(i<=S.length&&j<=T.length)
{
if(j==0||S.ch[i]==T.ch[j])
{
i++,j++;//匹配成功,i和j向后移動
}
else
{
j=next[j];//j回調(diào)可以直接匹配的位置
}
}
if(j>T.length) return i-T.length; //不需要+1,因?yàn)閣hile1循環(huán)退出之前i++,用來while循環(huán)判斷了
else return 0;
}
void get_nextval(String T,int nextval[])
{
int i=1,j=0;
while(i<T.length)
{
if(j==0||T.ch[i]==T.ch[j])
{
i++,j++;
if(T.ch[i]!=T.ch[j])
{
nextval[i]=j; //如果不相等正常賦值
}
else
{
nextval[i]=nextval[j]; //相等時
}
}
else
{
j=nextval[j];
}
}
}
int main()
{
String s1,s2; //s1母串,s2子串
char a[MAXLEN],b[MAXLEN];
cout<<"輸入母串:"<<endl; //aaabaaaab
cin>>s1.ch+1;
s1.length=strlen(s1.ch)-1;
cout<<"輸入子串:"<<endl;//aaaab
cin>>s2.ch+1;
s2.length=strlen(s2.ch)-1;
int next[MAXLEN];
get_nextval(s2,next);
cout<<"nextval數(shù)組如下"<<endl;
for(int i=1; i<=s2.length; i++)
{
cout<<next[i]<<" ";
}
cout<<endl;
printf("匹配位置:%d\n",Index_KMP(s1,s2,next));
return 0;
}
KMP算法復(fù)雜度分析
母串長n,模式串(子串)長m
首先我們分析一下暴力版本復(fù)雜度,i需要從1回退,2回退,3回退,一共回退n次,j每一次回退后都需要遍歷自身長度,那么就需要n乘以m次操作,O(nm)
kmp算法i并不會回退,所以i從1到n一共執(zhí)行n次操作故復(fù)雜度O(n),不要忘記還要求next數(shù)組的復(fù)雜度,求next數(shù)組,和kmp一樣都i都不會回溯,所以為O(m),故總時間復(fù)雜度O(n+m),這個復(fù)雜度在代碼上很好理解,尤其是考研版本的代碼,只需要一個while循環(huán)!
總結(jié)
整體來說kmp算法,初學(xué)復(fù)雜,尤其是對于next數(shù)組,不同求解,不同含義,容易讓人混淆,筆者在這里對next數(shù)組來龍去脈進(jìn)行貫穿講解,分成了競賽版,和考研版本,大家各取所需!競賽版本,next數(shù)組想法十分簡單,實(shí)現(xiàn)起來比考研版本復(fù)雜,但考研版本next數(shù)組含義復(fù)雜,代碼實(shí)現(xiàn)簡單,不過對i位置的理解容易懵掉,大家加油!!!文章來源：http://www.zghlxwxcb.cn/news/detail-480334.html
感謝大家觀看,感謝B站董曉算法,十分感謝!
董曉算法講解kmp文章來源地址http://www.zghlxwxcb.cn/news/detail-480334.html
到了這里，關(guān)于KMP算法(多種實(shí)現(xiàn)方式)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
