對(duì)于正常的字符串模式匹配，主串長度為m，子串為n，時(shí)間復(fù)雜度會(huì)到達(dá)O（m*n），而如果用KMP算法，復(fù)雜度將會(huì)減少線型時(shí)間O（m+n）。

設(shè)主串為ptr="ababaaababaa";，要比較的子串為a=“aab”；

KMP算法用到了next數(shù)組，然后利用next數(shù)組的值來提高匹配速度，我首先講一下next數(shù)組怎么求，之后再講匹配方式。

next數(shù)組詳解

首先是理解KMP算法的第一個(gè)難關(guān)是next數(shù)組每個(gè)值的確定，這個(gè)問題困惱我很長時(shí)間，尤其是對(duì)照著代碼一行一行分析，很容易把自己繞進(jìn)去。

定義一串字符串

ptr = "ababaaababaa";

next[i]（i從1開始算）代表著，除去第i個(gè)數(shù)，在一個(gè)字符串里面從第一個(gè)數(shù)到第（i-1）字符串前綴與后綴最長重復(fù)的個(gè)數(shù)。

什么是前綴？

在“aba”中，前綴就是“ab”，除去最后一個(gè)字符的剩余字符串。

同理可以理解后綴。除去第一個(gè)字符的后面全部的字符串。

在“aba”中，前綴是“ab”，后綴是“ba”，那么兩者最長的子串就是“a”；

在“ababa”中，前綴是“abab”，后綴是“baba”，二者最長重復(fù)子串是“aba”；

在“abcabcdabc”中，前綴是“abcabcdab”，后綴是“bcabcdabc”，二者最長重復(fù)的子串是“abc”；

這里有一點(diǎn)要注意，前綴必須要從頭開始算，后綴要從最后一個(gè)數(shù)開始算，中間截一段相同字符串是不行的。

再回到next[i]的定義，對(duì)于字符串ptr = "ababaaababaa";

next[1] = -1,代表著除了第一個(gè)元素，之前前綴后綴最長的重復(fù)子串，這里是空 ,即""，沒有，我們記為-1，代表空。（0代表1位相同，1代表兩位相同，依次累加）。

next[2] = -1，即“a”，沒有前綴與后綴，故最長重復(fù)的子串是空，值為-1；

next[3] = -1，即“ab”，前綴是“a”，后綴是“b”，最長重復(fù)的子串“”；

next[4] = 1，即"aba"，前綴是“ab”，后綴是“ba”，最長重復(fù)的子串“a”；next數(shù)組里面就是最長重復(fù)子串字符串的個(gè)數(shù)

next[5] = 2，即"abab"，前綴是“aba”，后綴是“bab”，最長重復(fù)的子串“ab”；

next[6] = 3，即"ababa"，前綴是“abab”，后綴是“baba”，最長重復(fù)的子串“aba”；

next[7] = 1，即"ababaa"，前綴是“ababa”，后綴是“babaa”，最長重復(fù)的子串“a”；

next[8] = 1，即"ababaaa"，前綴是“ababaa”，后綴是“babaaa”，最長重復(fù)的子串“a”；

next[9] = 2，即"ababaaab"，前綴是“ababaaa”，后綴是“babaaab”，最長重復(fù)的子串“ab”；

next[10] = 3，即"ababaaaba"，前綴是“ababaaab”，后綴是“babaaaba”，最長重復(fù)的子串“aba”；

next[11] = 4，即"ababaaabab"，前綴是“ababaaaba”，后綴是“babaaabab”，最長重復(fù)的子串“abab”；

next[12] = 5，即"ababaaababa"，前綴是“ababaaabab”，后綴是“babaaaababa”，最長重復(fù)的子串“ababa”；

還有另外一種方法，我看的有的書上寫著：

這里我們定義next[1] = 0 , next[1] = 1;

再分析ptr字符串，ptr = "ababaaababaa";

跟上一個(gè)的情況類似，

next[1] = 0 ,事先定義好的

next[2] = 1 ,事先定義好的

next[3] = 1 ,最長重復(fù)的子串“”；1代表沒有重復(fù)，2代表有一個(gè)字符重復(fù)。

next[4] = 2 ，最長重復(fù)的子串“a”；追償?shù)拈L度加1，即為2.

next[5] = 3 ，以下都跟之前的一樣，這種方法是最長的長度再加上一就可以了。

next[6] = 4

next[7] = 2

next[8] = 2

next[9] = 3

next[10] = 4

next[11] = 5

next[12] = 6

以上是next數(shù)組的詳細(xì)解釋。next數(shù)組求值 是比較麻煩的，剩下的匹配方式就很簡單了。

next數(shù)組用于子串身上，根據(jù)上面的原理，我們能夠推出子串a(chǎn)=“aab”的next數(shù)組的值分別為0,1,2.（按照我說的第二種方式算的）。

首先開始計(jì)算主串與子串的字符，設(shè)置主串用i來表示，子串用j來表示，如果ptr[i]與a[i]相等，那么i與j就都加1：

prt[1]與a[1]相等，i++，j++：

用代碼實(shí)現(xiàn)就是

if( j==0 ||  ptr[i]==a[j])
{
    ++i;
    ++j;
}

ptr[2]與a[2]不相等

此時(shí)ptr[2]!=a[2]，那么令j = next[j]，此時(shí)j=2，那么next[j] = next[2] = 1.那么此時(shí)j就等于1.這一段判斷用代碼解釋的話就是：

if( ptr[i]!=a[j])
{
      j = next[j];
}

加上上面的代碼進(jìn)行組合：

在對(duì)兩個(gè)數(shù)組進(jìn)行比對(duì)時(shí)，各自的i，j取值代碼：

while( i<ptr.length && j< a.length)
{
     if( j==0 || ptr[i]==a[i] )
    {
          ++i;
          ++j;

          next[i] = j;
    }
    else
    {
          j = next[j];
    }
}

此時(shí)將a[j]置于j此時(shí)所處的位置，即a[1]放到j(luò)=2處，因?yàn)樵趈=2時(shí)出現(xiàn)不匹配的情況。

此時(shí)再次計(jì)算是否匹配，可以看出來a[1]!=ptr[2],那么j = next[j]，即此時(shí)j = next[1] = 0;

根據(jù)上面的代碼，當(dāng)j=0時(shí)，執(zhí)行++i；++j；

此時(shí)就變?yōu)椋?/p>

此時(shí)ptr[3] = a[1],繼續(xù)向下走，下一個(gè)又不相等了，然后“aab”向后挪一位，這里不再贅述了，主要的思想已經(jīng)講明白了。到最后一直到i = 8，j=3時(shí)匹配成功，KMP算法結(jié)束。整個(gè)過程就結(jié)束了。

感謝打賞，手動(dòng)狗頭；)