傳統(tǒng)的字符串匹配算法中，為了在一段字符串中查找模式字符串的話需要使用2個(gè)循環(huán)嵌套起來，例如：
int i=0;
while(i< str.length()-parten.length())
{
int j=0;
while(parten[j]==str[i])
{
++i;
++j;
}
if(j==parten.length())
return true;
i=i-j+1;
}
return false;
這種方法很黃很暴力，其中對(duì)于第一個(gè)循環(huán)，會(huì)產(chǎn)生回溯。也就是說如果一個(gè)字符串：
bacbababaabcba來匹配模式字符串a(chǎn)bababa。當(dāng)原字符串的a和模式字符串的c做比較的時(shí)候，
|
b
|
a
|
c
|
b
|
a
|
b
|
a
|
b
|
a
|
a
(i=9)
|
b
|
c
|
b
|
a
|
|
|
|
|
|
a
|
b
|
a
|
b
|
a
|
b
(j=5)
|
a
|
|
|
|
當(dāng)發(fā)現(xiàn)不匹配的時(shí)候i會(huì)往前遞進(jìn)一位，此時(shí)從原字符串的第i+1位開始匹配字符串：
|
b
|
a
|
c
|
b
|
a
|
b
(i=5)
|
a
|
b
|
a
|
a
|
b
|
c
|
b
|
a
|
|
|
|
|
|
|
a
(j=0)
|
b
|
a
|
b
|
a
|
b
|
a
|
|
|
Kmp算法就是為了讓i不再回溯而提出的一種算法。在kmp算法中
當(dāng)匹配失敗后，i維持原來的值不變，只需要變動(dòng)j值即可。我們可以把j值直接加上一個(gè)位移忽略掉那些肯定會(huì)匹配失敗
的可能，現(xiàn)在的問題是如何求這個(gè)位移？
以模式字符串“abababa”為例子，位于字符串第3個(gè)位置的字母‘b’和要匹配的字符串T[0..k]做匹配運(yùn)算的時(shí)候，假如
匹配失敗，我們要尋求一個(gè)位移，目前我們所知道的條件有：
1、目前的情況下，j指向字符‘b’的位置，也就是3。
2、模式的前3個(gè)字符‘a’‘b’‘a’都匹配成功了，也就是說T[i-1]=‘a’；T[i-2]=‘b’；T[i-3]=‘a’。
3、匹配肯定是從i-3的位置開始的。
如果用最暴力的方法，那么把j從新置為0。但是我們注意到j(luò)=1的位置的字符和j=3的位置的字符是相同的。也就是說可以
直接從j=1重新開始比較而不是j=0。
通過總結(jié)歸納，可以得出：對(duì)于模式字符串中的每個(gè)字符計(jì)算出來的位移就是匹配模式字符串前綴的最長后綴的長度減一
（由于這里采用下標(biāo)從0計(jì)數(shù)的方法，所以還要減去1）。
匹配字符串前綴的最長后綴的長度減一。
匹配字符串前綴的最長后綴的長度減一。
這就是KMP算法唯一的奧秘了。
接下來，我們就可以不用考慮帶匹配的字符串的內(nèi)容，只需要根據(jù)模式字符串本身就可以求出每個(gè)字符如果匹配失敗后需
要位移的距離。計(jì)算完成后我們就可以得到一個(gè)整型的數(shù)組，數(shù)組的長度就是模式字符串的長度，數(shù)組中的每個(gè)元素就是每個(gè)
移動(dòng)到距離。
為了對(duì)模式字符串的每個(gè)字符求解移動(dòng)的距離，可以使用暴力的方法用2個(gè)循環(huán)的方法求得。仔細(xì)一看這又是一個(gè)字符串
匹配的方法，只不過匹配對(duì)象不一樣了。
這里先別急著求解移動(dòng)的距離，讓我們先假設(shè)我們計(jì)算出了每個(gè)字符要移動(dòng)的距離的數(shù)組next[]，如何來進(jìn)行字符匹配。
int i=0;
int j=0;
while(i< str.length()-parten.length())
{
while(j==0 || parten[j]==str[i])
{
++i;
++j;
}
if(j==parten.length())
return true;
j=next[j]; //next[]就是計(jì)算出來的要移動(dòng)距離
}
和前文的程序相比改動(dòng)灰常灰常的小。再也不需要去改變i的值，當(dāng)匹配不成功的時(shí)候只需要去取出預(yù)計(jì)算的next[]的值即可。
讓我們回到計(jì)算next[]的問題上來。根據(jù)前面得出的結(jié)論，我們需要找出匹配字符串前綴的最長后綴即可。考察字符串
“aba”，前綴可以是“a”、“ab”。后綴可以是“ba”、“a”。所以對(duì)于字符串“aba”的最后一個(gè)字母“a”它的next值
就是0。
再考察字符串“ababa”，前綴可以是“a”、“ab”、“aba”、“abab”。后綴可以是“baba”、“aba”、“ba”、
“a”。所以這里匹配的最長后綴是“aba”所以這個(gè)next值等于“aba”的長度減一等于2。
如果使用暴力的方法列舉每一個(gè)前綴和后綴比較的話，還是會(huì)遇到回溯的老問題。對(duì)于比較短的模式字符串的話效率尚
可，如果模式字符串的長度比較長的話就不太妙了。
在前面KMP的匹配算法中，由于我們知道了一個(gè)next[]數(shù)組，就正好知道了j跳轉(zhuǎn)的值，這里我們同樣可以使用這個(gè)方法。
假設(shè)在計(jì)算每個(gè)字符的next值的時(shí)候我們也使用2個(gè)循環(huán)，并且使用i控制下圖中上面的字符串的比較位置，用j控制下圖中下
面字符串的比較位置。
因?yàn)槲覀冃枰页銎ヅ淝熬Y的最大的后綴的長度，而對(duì)于一個(gè)字符串來說前綴和后綴的匹配至少需要相隔一個(gè)字符，如下
圖所示：
|
a
|
b (i=1)
|
a
|
b
|
|
|
|
|
|
|
a (j=0)
|
b
|
a
|
b
|
|
|
|
當(dāng)我們要找出字符串“abab”的最后一個(gè)字母‘b’的next值，那么就如同上圖一樣錯(cuò)開一位，如果不匹配，就把下面一
行的字符串向右再移動(dòng)一位：
|
a
|
b
|
a
|
b (i=3)
|
|
|
|
|
|
|
|
a
|
b (j=1)
|
a
|
b
|
|
|
這樣就正好匹配，得出next[3]=1。當(dāng)需要找出字符串“ababb”的最后一個(gè)字符next值的時(shí)候，是如下圖所示的場景：
|
a
|
b
|
a
|
b
|
b (i=4)
|
|
|
|
|
|
|
a
|
b
|
a (j=2)
|
b
|
a
|
|
發(fā)現(xiàn)不匹配，此時(shí)我們知道上一次匹配是成功的，所以可以讓j直接從上一次匹配成功的位置j=1。
|
a
|
b
|
a
|
b
|
b (i=4)
|
|
|
|
|
|
|
|
a
|
b (j=1)
|
a
|
b
|
a
|
這樣剛好得到匹配的后綴。得出next。
于是可以得出求得next[]的算法：
while (i<len)
{
while (j<0 || (i<len && B[i]==B[j]))
{
++i;
++j;
next[i]=j;
}
j=next[j];
}
我們注意到，這次比較還是c和a比較，而這次比較在上一次就已經(jīng)比較過了。所以為了避免這個(gè)比較，只需要把next的位于4的位置的值直接設(shè)置為next位于2的位置的值即可。那么計(jì)算next數(shù)組的算法如下：
while (i<len)
{
while (j<0 || (i<len && B[i]==B[j]))
{
++i;
++j;
If(B[i]==B[j])
next[i]=next[j];
else
next[i]=j;
}
j=next[j];
}
到此，又把數(shù)據(jù)結(jié)構(gòu)課本上的內(nèi)容啰唆了一次。
最后是完整的代碼，為了調(diào)試方便，加入了不少語句使得算法臃腫了不少。
#define INIT_POSISION 0
int KMP(const char* text,const char* parten_text)
{
unsigned int parten_len=strlen(parten_text);
unsigned int text_len=strlen(text);
int* nextArray=new int[parten_len];
findNext2(parten_text,nextArray);
int text_iterator=0;
int parten_iterator=0;
while (text_iterator<=text_len-parten_len) //如果剩下的字符長度小于模式的長度，就不用匹配了
{
char char_str=text[text_iterator];
char char_parten=parten_text[parten_iterator];
while (parten_iterator<=INIT_POSISION || (parten_iterator<parten_len &&
char_str==char_parten))
{
++text_iterator;
++parten_iterator;
char_str=text[text_iterator];
char_parten=parten_text[parten_iterator];
}
if (parten_iterator==parten_len) //完全匹配
{
return text_iterator-parten_len-1; //返回本次匹配的首字符位置
}
//沒有完全匹配，從next數(shù)組取下一個(gè)位置重新匹配
parten_iterator=nextArray[parten_iterator];
}
return INIT_POSISION;
}
void findNext2(const char* B,int* next)
{
int len=strlen(B);
next[ 0 ] = next[ 1 ] = -1 ;
int j=-1;
int i=0;
while (i<len)
{
while (j<0 || (i<len && B[i]==B[j]))
{
++i;
++j;
next[i]=j;
}
j=next[j];
}
for (int i=0;i<len;++i)
{
cout<<next[i]<<endl;
}
}