傳統的字符串匹配算法中，為了在一段字符串中查找模式字符串的話需要使用2個循環嵌套起來，例如：
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;
這種方法很黃很暴力，其中對于第一個循環，會產生回溯。也就是說如果一個字符串：
bacbababaabcba來匹配模式字符串abababa。當原字符串的a和模式字符串的c做比較的時候，
|
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
|
|
|
|
當發現不匹配的時候i會往前遞進一位，此時從原字符串的第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算法中
當匹配失敗后，i維持原來的值不變，只需要變動j值即可。我們可以把j值直接加上一個位移忽略掉那些肯定會匹配失敗
的可能，現在的問題是如何求這個位移？
以模式字符串“abababa”為例子，位于字符串第3個位置的字母‘b’和要匹配的字符串T[0..k]做匹配運算的時候，假如
匹配失敗，我們要尋求一個位移，目前我們所知道的條件有：
1、目前的情況下，j指向字符‘b’的位置，也就是3。
2、模式的前3個字符‘a’‘b’‘a’都匹配成功了，也就是說T[i-1]=‘a’；T[i-2]=‘b’；T[i-3]=‘a’。
3、匹配肯定是從i-3的位置開始的。
如果用最暴力的方法，那么把j從新置為0。但是我們注意到j=1的位置的字符和j=3的位置的字符是相同的。也就是說可以
直接從j=1重新開始比較而不是j=0。
通過總結歸納，可以得出：對于模式字符串中的每個字符計算出來的位移就是匹配模式字符串前綴的最長后綴的長度減一
（由于這里采用下標從0計數的方法，所以還要減去1）。
匹配字符串前綴的最長后綴的長度減一。
匹配字符串前綴的最長后綴的長度減一。
這就是KMP算法唯一的奧秘了。
接下來，我們就可以不用考慮帶匹配的字符串的內容，只需要根據模式字符串本身就可以求出每個字符如果匹配失敗后需
要位移的距離。計算完成后我們就可以得到一個整型的數組，數組的長度就是模式字符串的長度，數組中的每個元素就是每個
移動到距離。
為了對模式字符串的每個字符求解移動的距離，可以使用暴力的方法用2個循環的方法求得。仔細一看這又是一個字符串
匹配的方法，只不過匹配對象不一樣了。
這里先別急著求解移動的距離，讓我們先假設我們計算出了每個字符要移動的距離的數組next[]，如何來進行字符匹配。
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[]就是計算出來的要移動距離
}
和前文的程序相比改動灰常灰常的小。再也不需要去改變i的值，當匹配不成功的時候只需要去取出預計算的next[]的值即可。
讓我們回到計算next[]的問題上來。根據前面得出的結論，我們需要找出匹配字符串前綴的最長后綴即可。考察字符串
“aba”，前綴可以是“a”、“ab”。后綴可以是“ba”、“a”。所以對于字符串“aba”的最后一個字母“a”它的next值
就是0。
再考察字符串“ababa”，前綴可以是“a”、“ab”、“aba”、“abab”。后綴可以是“baba”、“aba”、“ba”、
“a”。所以這里匹配的最長后綴是“aba”所以這個next值等于“aba”的長度減一等于2。
如果使用暴力的方法列舉每一個前綴和后綴比較的話，還是會遇到回溯的老問題。對于比較短的模式字符串的話效率尚
可，如果模式字符串的長度比較長的話就不太妙了。
在前面KMP的匹配算法中，由于我們知道了一個next[]數組，就正好知道了j跳轉的值，這里我們同樣可以使用這個方法。
假設在計算每個字符的next值的時候我們也使用2個循環，并且使用i控制下圖中上面的字符串的比較位置，用j控制下圖中下
面字符串的比較位置。
因為我們需要找出匹配前綴的最大的后綴的長度，而對于一個字符串來說前綴和后綴的匹配至少需要相隔一個字符，如下
圖所示：
|
a
|
b (i=1)
|
a
|
b
|
|
|
|
|
|
|
a (j=0)
|
b
|
a
|
b
|
|
|
|
當我們要找出字符串“abab”的最后一個字母‘b’的next值，那么就如同上圖一樣錯開一位，如果不匹配，就把下面一
行的字符串向右再移動一位：
|
a
|
b
|
a
|
b (i=3)
|
|
|
|
|
|
|
|
a
|
b (j=1)
|
a
|
b
|
|
|
這樣就正好匹配，得出next[3]=1。當需要找出字符串“ababb”的最后一個字符next值的時候，是如下圖所示的場景：
|
a
|
b
|
a
|
b
|
b (i=4)
|
|
|
|
|
|
|
a
|
b
|
a (j=2)
|
b
|
a
|
|
發現不匹配，此時我們知道上一次匹配是成功的，所以可以讓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比較，而這次比較在上一次就已經比較過了。所以為了避免這個比較，只需要把next的位于4的位置的值直接設置為next位于2的位置的值即可。那么計算next數組的算法如下：
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];
}
到此，又把數據結構課本上的內容啰唆了一次。
最后是完整的代碼，為了調試方便，加入了不少語句使得算法臃腫了不少。
#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數組取下一個位置重新匹配
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;
}
}