說(shuō)明
KMP算法看懂了覺(jué)得特別簡(jiǎn)單屉栓，思路很簡(jiǎn)單羊赵，看不懂之前趟佃，查各種資料，看的稀里糊涂昧捷，即使網(wǎng)上最簡(jiǎn)單的解釋?zhuān)廊豢吹南±锖俊?
我花了半天時(shí)間闲昭，爭(zhēng)取用最短的篇幅大致搞明白這玩意到底是啥。?
這里不扯概念靡挥，只講算法過(guò)程和代碼理解：
字符串匹配序矩。給你兩個(gè)字符串，尋找其中一個(gè)字符串是否包含另一個(gè)字符串跋破，如果包含簸淀，返回包含的起始位置。?
如下面兩個(gè)字符串：
char*str="bacbababadababacambabacaddababacasdsd";char*ptr ="ababaca";
1
2
str有兩處包含ptr?
分別在str的下標(biāo)10幔烛，26處包含ptr啃擦。
“bacbababadababacambabacaddababacasdsd”;\?
問(wèn)題類(lèi)型很簡(jiǎn)單，下面直接介紹算法
一般匹配字符串時(shí)饿悬，我們從目標(biāo)字符串str（假設(shè)長(zhǎng)度為n）的第一個(gè)下標(biāo)選取和ptr長(zhǎng)度（長(zhǎng)度為m）一樣的子字符串進(jìn)行比較令蛉，如果一樣，就返回開(kāi)始處的下標(biāo)值狡恬，不一樣珠叔，選取str下一個(gè)下標(biāo)，同樣選取長(zhǎng)度為n的字符串進(jìn)行比較弟劲，直到str的末尾（實(shí)際比較時(shí)祷安，下標(biāo)移動(dòng)到n-m）。這樣的時(shí)間復(fù)雜度是O(n*m)兔乞。
KMP算法：可以實(shí)現(xiàn)復(fù)雜度為O(m+n)
為何簡(jiǎn)化了時(shí)間復(fù)雜度：?
充分利用了目標(biāo)字符串ptr的性質(zhì)（比如里面部分字符串的重復(fù)性汇鞭，即使不存在重復(fù)字段，在比較時(shí)庸追，實(shí)現(xiàn)最大的移動(dòng)量）霍骄。?
上面理不理解無(wú)所謂，我說(shuō)的其實(shí)也沒(méi)有深刻剖析里面的內(nèi)部原因淡溯。
考察目標(biāo)字符串ptr：?
ababaca?
這里我們要計(jì)算一個(gè)長(zhǎng)度為m的轉(zhuǎn)移函數(shù)next读整。
next數(shù)組的含義就是一個(gè)固定字符串的最長(zhǎng)前綴和最長(zhǎng)后綴相同的長(zhǎng)度。
比如：abcjkdabc咱娶，那么這個(gè)數(shù)組的最長(zhǎng)前綴和最長(zhǎng)后綴相同必然是abc米间。?
cbcbc强品，最長(zhǎng)前綴和最長(zhǎng)后綴相同是cbc。?
abcbc屈糊，最長(zhǎng)前綴和最長(zhǎng)后綴相同是不存在的的榛。
**注意最長(zhǎng)前綴：是說(shuō)以第一個(gè)字符開(kāi)始，但是不包含最后一個(gè)字符另玖。?
比如aaaa相同的最長(zhǎng)前綴和最長(zhǎng)后綴是aaa困曙。**?
對(duì)于目標(biāo)字符串ptr，ababaca谦去，長(zhǎng)度是7慷丽，所以next[0]，next[1]鳄哭，next[2]要糊，next[3]，next[4]妆丘，next[5]锄俄，next[6]分別計(jì)算的是?
a，ab勺拣，aba奶赠，abab，ababa药有，ababac毅戈，ababaca的相同的最長(zhǎng)前綴和最長(zhǎng)后綴的長(zhǎng)度。由于a愤惰，ab苇经，aba，abab宦言，ababa扇单，ababac，ababaca的相同的最長(zhǎng)前綴和最長(zhǎng)后綴是“”奠旺，“”蜘澜，“a”，“ab”响疚，“aba”兼都，“”，“a”,所以next數(shù)組的值是[-1,-1,0,1,2,-1,0]稽寒，這里-1表示不存在，0表示存在長(zhǎng)度為1趟章，2表示存在長(zhǎng)度為3杏糙。這是為了和代碼相對(duì)應(yīng)慎王。
下圖中的1，2宏侍，3赖淤，4是一樣的。1-2之間的和3-4之間的也是一樣的谅河，我們發(fā)現(xiàn)A和B不一樣咱旱；之前的算法是我把下面的字符串往前移動(dòng)一個(gè)距離，重新從頭開(kāi)始比較绷耍，那必然存在很多重復(fù)的比較⊥孪蓿現(xiàn)在的做法是，我把下面的字符串往前移動(dòng)褂始，使3和2對(duì)其诸典，直接比較C和A是否一樣。
voidcal_next(char*str,int*next,intlen){? ? next[0] = -1;//next[0]初始化為-1崎苗，-1表示不存在相同的最大前綴和最大后綴intk = -1;//k初始化為-1for(intq =1; q <= len-1; q++)? ? {while(k > -1&&str[k +1] !=str[q])//如果下一個(gè)不同狐粱，那么k就變成next[k]，注意next[k]是小于k的胆数，無(wú)論k取任何值肌蜻。{? ? ? ? ? ? k = next[k];//往前回溯}if(str[k +1] ==str[q])//如果相同，k++{? ? ? ? ? ? k = k +1;? ? ? ? }? ? ? ? next[q] = k;//這個(gè)是把算的k的值（就是相同的最大前綴和最大后綴長(zhǎng)）賦給next[q]}}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
這個(gè)和next很像必尼，具體就看代碼蒋搜，其實(shí)上面已經(jīng)大概說(shuō)完了整個(gè)匹配過(guò)程。
intKMP(char*str,intslen,char*ptr,intplen){int*next =newint[plen];? ? cal_next(ptr, next, plen);//計(jì)算next數(shù)組intk = -1;for(inti =0; i < slen; i++)? ? {while(k >-1&& ptr[k +1] !=str[i])//ptr和str不匹配胰伍，且k>-1（表示ptr和str有部分匹配）k = next[k];//往前回溯if(ptr[k +1] ==str[i])? ? ? ? ? ? k = k +1;if(k == plen-1)//說(shuō)明k移動(dòng)到ptr的最末端{(lán)//cout << "在位置" << i-plen+1<< endl;//k = -1;//重新初始化齿诞，尋找下一個(gè)//i = i - plen + 1;//i定位到該位置，外層for循環(huán)i++可以繼續(xù)找下一個(gè)（這里默認(rèn)存在兩個(gè)匹配字符串可以部分重疊）骂租，感謝評(píng)論中同學(xué)指出錯(cuò)誤祷杈。returni-plen+1;//返回相應(yīng)的位置}? ? }return-1;? }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
char*str="bacbababadababacambabacaddababacasdsd";char*ptr ="ababaca";inta = KMP(str,36, ptr,7);return0;
1
2
3
4
注意如果str里有多個(gè)匹配ptr的字符串，要想求出所有的滿足要求的下標(biāo)位置渗饮，在KMP算法需要稍微修改一下但汞。見(jiàn)上面注釋掉的代碼。
next函數(shù)計(jì)算復(fù)雜度是(m)互站，開(kāi)始以為是O(m^2)私蕾，后來(lái)仔細(xì)想了想，cal__next里的while循環(huán)胡桃，以及外層for循環(huán)踩叭，利用均攤思想，其實(shí)是O(m)，這個(gè)以后想好了再寫(xiě)上容贝。
………………………………………..分割線……………………………………..?
其實(shí)本文已經(jīng)結(jié)束自脯，后面的只是針對(duì)評(píng)論里的疑問(wèn)，我嘗試著進(jìn)行解答的斤富。
看了評(píng)論膏潮，大家對(duì)cal_next(..)函數(shù)和KMP()函數(shù)里的
while(k > -1&&str[k +1] !=str[q])? ? ? ? {? ? ? ? ? ? k = next[k];? ? ? ? }
1
2
3
4
和
while(k >-1&& ptr[k +1] != str[i])? ? ? ? ? ? k =next[k];
1
2
這個(gè)while循環(huán)和k=next[k]很疑惑！?
確實(shí)啊满力，我開(kāi)始看這幾行代碼焕参，相當(dāng)懵逼，這寫(xiě)的啥啊油额，為啥這樣寫(xiě)叠纷；后來(lái)上機(jī)跑了一下，慢慢了解到為何這樣寫(xiě)了悔耘。這幾行代碼讲岁，可謂是對(duì)KMP算法本質(zhì)得了解非常清楚才能想到的。很牛逼衬以！?
直接看cal_next(..)函數(shù)：?
首先我們看第一個(gè)while循環(huán)缓艳，它到底干了什么。
在此之前看峻，我們先回到原程序阶淘。原程序里有一個(gè)大的for()循環(huán)，那這個(gè)for()循環(huán)是干嘛的互妓？
這個(gè)for循環(huán)就是計(jì)算next[0]溪窒，next[1],…next[q]…的值。
里面最后一句next[q]=k就是說(shuō)明每次循環(huán)結(jié)束冯勉，我們已經(jīng)計(jì)算了ptr的前(q+1)個(gè)字母組成的子串的“相同的最長(zhǎng)前綴和最長(zhǎng)后綴的長(zhǎng)度”澈蚌。（這句話前面已經(jīng)解釋了！） 這個(gè)“長(zhǎng)度”就是k灼狰。
好宛瞄，到此為止，假設(shè)循環(huán)進(jìn)行到 第 q 次交胚，即已經(jīng)計(jì)算了next[q]份汗，我們是怎么計(jì)算next[q+1]呢？
比如我們已經(jīng)知道ababab蝴簇，q=4時(shí)杯活，next[4]=2（k=2，表示該字符串的前5個(gè)字母組成的子串ababa存在相同的最長(zhǎng)前綴和最長(zhǎng)后綴的長(zhǎng)度是3熬词，所以k=2,next[4]=2旁钧。這個(gè)結(jié)果可以理解成我們自己觀察算的吸重，也可以理解成程序自己算的，這不是重點(diǎn)歪今，重點(diǎn)是程序根據(jù)目前的結(jié)果怎么算next[5]的）.晤锹，那么對(duì)于字符串ababab，我們計(jì)算next[5]的時(shí)候彤委，此時(shí)q=5, k=2（上一步循環(huán)結(jié)束后的結(jié)果）。那么我們需要比較的是str[k+1]和str[q]是否相等或衡，其實(shí)就是str[1]和str[5]是否相等焦影！，為啥從k+1比較呢封断，因?yàn)樯弦淮窝h(huán)中斯辰，我們已經(jīng)保證了str[k]和str[q]（注意這個(gè)q是上次循環(huán)的q）是相等的（這句話自己想想，很容易理解）坡疼，所以到本次循環(huán)彬呻，我們直接比較str[k+1]和str[q]是否相等（這個(gè)q是本次循環(huán)的q）。?
如果相等柄瑰，那么跳出while()闸氮，進(jìn)入if()，k=k+1教沾，接著next[q]=k蒲跨。即對(duì)于ababab，我們會(huì)得出next[5]=3授翻。 這是程序自己算的或悲，和我們觀察的是一樣的。?
如果不等堪唐，我們可以用”ababac“描述這種情況巡语。 不等，進(jìn)入while()里面淮菠，進(jìn)行k=next[k]男公，這句話是說(shuō)，在str[k + 1] != str[q]的情況下兜材，我們往前找一個(gè)k理澎，使str[k + 1]==str[q]，是往前一個(gè)一個(gè)找呢曙寡，還是有更快的找法呢糠爬？ （一個(gè)一個(gè)找必然可以，即你把 k = next[k] 換成k- -也是完全能運(yùn)行的（更正：這句話不對(duì)啊举庶，把k=next[k]換成k–是不行的执隧，評(píng)論25樓舉了個(gè)反例）。但是程序給出了一種更快的找法，那就是 k = next[k]镀琉。 程序的意思是說(shuō)峦嗤，一旦str[k + 1] != str[q]，即在后綴里面找不到時(shí)屋摔，我是可以直接跳過(guò)中間一段烁设，跑到前綴里面找，next[k]就是相同的最長(zhǎng)前綴和最長(zhǎng)后綴的長(zhǎng)度钓试。所以装黑，k=next[k]就變成，k=next[2]弓熏，即k=0恋谭。此時(shí)再比較str[0+1]和str[5]是否相等，不等挽鞠，則k=next[0]=-1疚颊。跳出循環(huán)。?
（這個(gè)解釋能懂不信认？）
以上就是這個(gè)cal_next()函數(shù)里的
while(k > -1&&str[k +1] !=str[q])? ? ? ? {? ? ? ? ? ? k = next[k];? ? ? ? }
1
2
3
4
最難理解的地方的一個(gè)我的理解材义，有不對(duì)的歡迎指出。
復(fù)雜度分析：
分析KMP復(fù)雜度狮杨，那就直接看KMP函數(shù)母截。
intKMP(char*str,intslen,char*ptr,intplen){int*next =newint[plen];? ? cal_next(ptr, next, plen);//計(jì)算next數(shù)組intk = -1;for(inti =0; i < slen; i++)? ? {while(k >-1&& ptr[k +1] !=str[i])//ptr和str不匹配，且k>-1（表示ptr和str有部分匹配）k = next[k];//往前回溯if(ptr[k +1] ==str[i])? ? ? ? ? ? k = k +1;if(k == plen-1)//說(shuō)明k移動(dòng)到ptr的最末端{(lán)//cout << "在位置" << i-plen+1<< endl;//k = -1;//重新初始化橄教，尋找下一個(gè)//i = i - plen + 1;//i定位到該位置清寇，外層for循環(huán)i++可以繼續(xù)找下一個(gè)（這里默認(rèn)存在兩個(gè)匹配字符串可以部分重疊），感謝評(píng)論中同學(xué)指出錯(cuò)誤护蝶。returni-plen+1;//返回相應(yīng)的位置}? ? }return-1;? }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
這玩意真的不好解釋?zhuān)?jiǎn)單說(shuō)一下：?
從代碼解釋復(fù)雜度是一件比較難的事情华烟，我們從?
這個(gè)圖來(lái)解釋。
我們可以看到持灰，匹配串每次往前移動(dòng)盔夜，都是一大段一大段移動(dòng)，假設(shè)匹配串里不存在重復(fù)的前綴和后綴堤魁，即next的值都是-1喂链，那么每次移動(dòng)其實(shí)就是一整個(gè)匹配串往前移動(dòng)m個(gè)距離。然后重新一一比較妥泉，這樣就比較m次椭微，概括為，移動(dòng)m距離盲链，比較m次蝇率，移到末尾迟杂，就是比較n次，O(n)復(fù)雜度本慕。 假設(shè)匹配串里存在重復(fù)的前綴和后綴排拷，我們移動(dòng)的距離相對(duì)小了點(diǎn)，但是比較的次數(shù)也小了锅尘，整體代價(jià)也是O(n)监氢。?
所以復(fù)雜度是一個(gè)線性的復(fù)雜度。
