生活随笔
收集整理的這篇文章主要介紹了
KMP及其改进算法
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
本文主要講述KMP已經(jīng)KMP的一種改進(jìn)方法。若發(fā)現(xiàn)不正確的地方，歡迎交流指出，謝謝！
KMP算法的基本思想:
KMP的算法流程:
每當(dāng)一趟匹配過程中出現(xiàn)字符比較不等時(shí)，不需回溯 i 指針，而是利用已經(jīng)得到的部分匹配的結(jié)果將模式向右滑動(dòng)盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。
設(shè)S為目標(biāo)串 ，T為模式串 ，設(shè) i 指針和 j 指針分別指示目標(biāo)串和模式串中正待比較的字符。
開始時(shí)，令i=0，j=0。如果Si==Tj，則使i和j的值分別增加l；反之，i不變，j的值退回到j(luò)=next[j]的位置(即模式串右滑)，然后再對(duì)Si和Tj進(jìn)行比較。依次類推，直到出現(xiàn)下列兩種情況之一 ：
1．j值退回到某個(gè)j=next[j]時(shí)，有 Si==Tj ，則指針的值各增加1后，再繼續(xù)匹配；
2．j值退回到 j=-1，此時(shí)令指針的值各增加1，也即下一次對(duì)Si+1和T0進(jìn)行比較。
模式匹配KMP算法的時(shí)間復(fù)雜度為O(m+n)，
跟樸素匹配算法的主要差異：
???在于當(dāng)Si != Tj的時(shí)候，樸素算法采用的是將Tj往前推一格，然后將j置為0，重新進(jìn)行匹配，而KMP采用的方法是將j置為next[j]，然后再匹配。
很顯然，這里的next[j]是算法的核心
下面是next[j]的計(jì)算方法，以及代碼的實(shí)現(xiàn)：
[cpp] ?view plaincopy
void ?get_nextval(? const ? char ?*s,? int ?*nextval)?? {?? ?????int ?len?=?strlen(s);?????? ?????int ?i?=?0,?j?=?-1;?? ?? ?????nextval[0]?=?-1;?????? ?? ?????while (?i?<?len-1?){?? ??????????if (?j?==?-1?||?s[i]?==?s[j]?){?? ???????????????++i;?????? ???????????????++j;?????? ?? ???????????????if (?s[i]?!=?s[j]?){?? ????????????????????nextval[i]?=?j;?????? ???????????????}else {?? ????????????????????nextval[i]?=?nextval[j];?????? ???????????????}?? ??????????}else {?? ???????????????j?=?nextval[j];?????? ??????????}?? ?????}?? ?? ?????return ?;?????? }??
得到了next[j]之后，KMP算法的實(shí)現(xiàn)就很簡(jiǎn)單了，按照上面KMP的算法流程，可以很快寫出代碼：
[cpp] ?view plaincopy
?? ?? int ?kmp(? const ? char ?*s,? const ? char ?*t?)?? {?? ?????int ?k?=?-1;?????? ?????int ?nextval[N]?=?{0};?????? ?????int ?s_len?=?strlen(s);?????? ?????int ?t_len?=?strlen(t);?????? ?? ?????get_nextval(?s,?nextval?);??????? ?????cout<<"nextval:" <<endl;?????? ?????for (?k?=?0;?k?<?s_len;?k++)?? ??????????cout<<nextval[k]<<"?" ;?????? ?????cout<<endl;?????? ?? ?????int ?i?=?0,?j?=?0;?????? ?????? ?? ?????while (?i?<?t_len?&&?j?<?s_len?){?? ??????????if (?j?==?-1?||?t[i]?==?s[j]?){?? ???????????????i++;?????? ???????????????j++;?????? ??????????}else {?? ???????????????j?=?nextval[j];?????? ??????????}?? ?????}?? ?? ?? ?????if (?j?>=?s_len?){?? ??????????return ?i-s_len;?????? ?????}else {?? ??????????return ?-1;?????? ?????}?? }??
下面給出一個(gè)KMP的實(shí)現(xiàn)及測(cè)試代碼：
[cpp] ?view plaincopy
#include?<iostream> ?? using ? namespace ?std;?????? #define?N?100 ?? ?? void ?get_nextval(? const ? char ?*s,? int ?*nextval);?????? int ?kmp(? const ? char ?*s,? const ? char ?*t?);?????? ?? ?? ?? ?? int ?kmp(? const ? char ?*s,? const ? char ?*t?)?? {?? ?????int ?k?=?-1;?????? ?????int ?nextval[N]?=?{0};?????? ?????int ?s_len?=?strlen(s);?????? ?????int ?t_len?=?strlen(t);?????? ?? ?????get_nextval(?s,?nextval?);??????? ?????cout<<"nextval:" <<endl;?????? ?????for (?k?=?0;?k?<?s_len;?k++)?? ??????????cout<<nextval[k]<<"?" ;?????? ?????cout<<endl;?????? ?? ?????int ?i?=?0,?j?=?0;?????? ?????? ?? ?????while (?i?<?t_len?&&?j?<?s_len?){?? ??????????if (?j?==?-1?||?t[i]?==?s[j]?){?? ???????????????i++;?????? ???????????????j++;?????? ??????????}else {?? ???????????????j?=?nextval[j];?????? ??????????}?? ?????}?? ?? ?? ?????if (?j?>=?s_len?){?? ??????????return ?i-s_len;?????? ?????}else {?? ??????????return ?-1;?????? ?????}?? }?? ?? void ?get_nextval(? const ? char ?*s,? int ?*nextval)?? {?? ?????int ?len?=?strlen(s);?????? ?????int ?i?=?0,?j?=?-1;?? ?? ?????nextval[0]?=?-1;?????? ?? ?????while (?i?<?len-1?){?? ??????????if (?j?==?-1?||?s[i]?==?s[j]?){?? ???????????????++i;?????? ???????????????++j;?????? ?? ???????????????if (?s[i]?!=?s[j]?){?? ????????????????????nextval[i]?=?j;?????? ???????????????}else {?? ????????????????????nextval[i]?=?nextval[j];?????? ???????????????}?? ??????????}else {?? ???????????????j?=?nextval[j];?????? ??????????}?? ?????}?? ?? ?????return ?;?????? }?? ?? int ?main()?? {?? ?????char ?s[N],?t[N];?????? ?????while (?cin>>s?>>t?){?? ??????????int ?i?=?0;?????? ??????????i?=?kmp(?s,?t?);?????? ?? ??????????cout?<<"ans?=?" ?<<i?<<endl;?????? ?????}?? ?????return ?0;?????? }??
測(cè)試如下：
KMP模式匹配問題的改進(jìn)思想和方法
KMP的不足之處：
??? 通過觀察，我們可以在原有的KMP算法中，發(fā)現(xiàn)一個(gè)不 足的地方 如果子串在主串出現(xiàn)的位置靠后的時(shí)候，KMP 算法實(shí)在顯得比較低效
?
主串為：aspowqeursoolksnkhiozbgwoinpweuirabaac
子串為：abaac
?
??? 容易看出，子串要到最后才會(huì)得到匹配，因此，我們提出我們的思想——從主串的首和尾同時(shí)進(jìn)行匹配，那樣，就可以提高算法的效率，并且，除了在這個(gè)方面提高算法效率以外，我們還想到，當(dāng) m >>n，，n>>0的時(shí)候(m為主串長(zhǎng)度，n為子串長(zhǎng)度)，并且子串并沒有在主串中出現(xiàn)的話，那么，在改進(jìn)算法中，我們將不需要比較到最末才判斷是否存在匹配的子串，而是通過剩下的字符數(shù)，來(lái)判斷是否存在足夠的字符與子串匹配，如果不足的話，那樣就不存在，否則就繼續(xù)匹配下去。
如何實(shí)現(xiàn)從主串末尾想串頭開始匹配呢?
??? 我們這里有兩個(gè)方案：第一個(gè)方案 是，把子串逆轉(zhuǎn)，然后沿用舊的KMP算法中的next函數(shù)求出其逆轉(zhuǎn)后的子串的next值，再用以進(jìn)行匹配；第二個(gè)方案 就是，不需要把子串逆轉(zhuǎn)，而是采用一個(gè)新的next函數(shù)直接求出其逆轉(zhuǎn)后的next值。
??? 第一二個(gè)方案比較后，我們選擇第二個(gè)方案。因?yàn)?#xff0c;在 n>>0的時(shí)候，明顯地，在把子串逆轉(zhuǎn)的時(shí)候同時(shí)需要多一個(gè)字符串來(lái)存放，并且，在不同的匹配都需要一個(gè)新的字符串，這樣就大大地浪費(fèi)空間了,除此之外，第一個(gè)方案至少要做遍歷子串兩次，而第二個(gè)方案只需要遍歷子串一次就可以了。所以我們決定采用構(gòu)建一個(gè)新的next函數(shù)來(lái)求出其逆轉(zhuǎn)后的子串next值。
??? 我們新的next函數(shù)的思想就是，把末字符看成是首字符，然后，仿照KMP算法中的next函數(shù)的實(shí)現(xiàn)方式最終實(shí)現(xiàn)的。現(xiàn)在，我們給出實(shí)現(xiàn)的新的next函數(shù)：
[cpp] ?view plaincopy
void ?nextres(? char *?p,? int ?*next,? int ?n?)?? {?? ????????int ?i,?j,?k;?????? ????????i?=?n-1,?j?=?-1;?????????? ????????*next?=?-1;??????? ????????k?=?n;???? ????????while (?i?>?0?){?? ????????????????if (?j?==?-1?||?*(p+i)?==?*(p+k-j-1)){?? ????????????????????????i--,?j++;????????? ????????????????????????if (?*(p+i)?!=?*(p+k-j-1)?)?? ????????????????????????????????*(next+n-i-1)?=?j;???????? ????????????????????????else ?? ????????????????????????????????*(next+n-i-1)?=?*(next+j);???????? ????????????????}?? ????????????????else ??? ????????????????????????j?=?*(next+j);???? ????????}?? ?? }??
[cpp] ?view plaincopy
int ?march(? char *?mainhead,? char *?head,? int ?mainlen,? int ?lenth,? int ?*next1,? int ?*next2?)?? {?? ????????int ?i,?j,?k,?l,?m;???????? ????????i?=?0,?j?=?0,?k?=?mainlen-1,?m?=?lenth-1,?l?=?0;?????????? ????????while (?(m>0?&&?j<lenth)?||?lenth?==?1?){?? ????????????????if (?lenth?==?1?&&?(?*(mainhead+i)?==?*(head+j)?||?? ????????????????????????*(mainhead+k)?==?*(head+m)))?? ????????????????????????return ?1;????????? ????????????????if (?j?==?-1?||?*(mainhead+i)?==?*(head+j))?? ????????????????????????i++,?j++;????????? ????????????????else ?? ????????????????????????j?=?*(next1+j);??? ????????????????if (?l?==?-1?||?*(mainhead+k)?==?*(head+m)){?? ????????????????????????k--;?? ????????????????????????l++;?? ????????????????????????m?=?lenth==2?m-l:m-1;????? ????????????????}else {?? ????????????????????????l?=?*(next2+1);??? ????????????????????????if (?l?!=?-1?)?? ????????????????????????????????m?=?m-l;?????????? ????????????????????????else ?? ????????????????????????????????m?=?lenth-1;?????? ????????????????}?? ????????????????if (?k-i?<?m-j?)?? ????????????????????????return ?0;????????? ????????}?? ?? ????????if (?m?<=?0?||?j?>=?lenth)?? ????????????????return ?1;????????? ????????else ??? ????????????????return ?0;????????? }??
新的KMP算法在某種程度上的確可以提高模式匹配的效率。除此以外，新的模式匹配算法還能提早結(jié)束不必要的匹配 。
from:?http://blog.csdn.net/cyh_24/article/details/8162436
總結(jié)
以上是生活随笔 為你收集整理的KMP及其改进算法 的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔 推薦給好友。
