KMP演演算法

  首先KMP演演算法是基於next函數而實現的，與BF演演算法相比，KMP演演算法是沒有了主串指標回溯的情況。改進後的演演算法複雜度為O(m+n).

KMP演演算法的簡述
  每一次比較時，當子串與主串不相等的時候，主串的指標不回溯，而是通過next函數所求得的值當作下一位子串開始比較的位置。(即儘可能地向右邊滑動一段的距離，從而減少比較的次數)。

KMP演演算法匹配過程範例    第一趟匹配：   a   b    a   b   c   a   b   c   a   c   b   a   b
           a   b    c   a   c

   第二趟匹配：   a   b   a   b   c   a    b   c   a   c   b   a   b
             a   b   c   a    c

   第三趟匹配：   a   b   a   b   c   a   b   c   a    c   b   a   b
                  a   b   c   a    c
  首先要解決的是，當主串和子串失配的時候子串要向後 滑動多少，這就要說到 next函數了， next函數就是計運算元串每一位失配的時候應該向後滑動多少。
   假設此時匹配的關係如下:

    S = S1 S2 ... S(i-j+1) S(i-j+2)... S(i-k+1) ... S(i-1)  S(i) ... S(n)
    T =         T1  T2 ...  T(j-k+1) ... T(j-1)  T(j) ... 
    T =                  T1 ...   T(k-1)  T(k) ... 

  由上圖可以看出來當 S(i)與 T(j)不相等時，從 T(j)前面的真子串開始尋找最大匹配的真字首子串和字尾子串，若如圖所示最長的真字首子串和字尾子串為 K-1,對比 KMP演演算法範例圖，可以看出只需要 滑動使得T(k)與S(i)對齊即可，因為是最大的真字首子串和最大的真字尾子串，所以當前子串匹配的位置前面的字元，一定與主串對應位置的各個字元相等，這樣子滑動子串就避免了主串指標的不斷回溯。
  設next[j] = k,則 next[j]表示當子串與主串失配的時候，子串下一位與主串相比的元素的下標。
  因此我們可以得到 next的函數:
  當j = 1時，說明當前處於子串的第一個有效值的位置，前面的真子串長度為0，所以next[j] = 0
  當位於其他位置的時候，next[j]的值就是目前已匹配的最長的真字首子串的下一位。
  每一次 滑動的位數就是當前子串不匹配的位置，前面的 真字首子串和 真字尾子串所相等時的最大子串的長度加1。
   實際上我們會發現子串滑動的位數與主串並沒有什麼關係
KMP演演算法程式碼

int Index_KMP(SString *S, int pos, SString *T) {


	int next[MAXSIZE] ;
	Get_Next( T, next);
	int i = pos, j = 1;
	while(i <= S->len && j <= T->len) {
		if(S->data[i] == T->data[j] || j == 0) {
			//j == 0是一個判斷條件，當子串匹配到第一個字元的時候都沒有匹配
			//子串與主串的指標都要向後移動，重新從頭開始進行匹配
			++i;
			++j;
		} else {
			j = next[j];
		}
		
	}
	if(j > T->len)
		return(i - T->len);
	else
		return 0;

}

next演演算法的描述
  首先next函數是基於遞推的思想的，KMP演演算法是基於next函數來實現的。

next的函數值，由上述的定義可以得到next[1] = 0,假設next[j] = k,說明最長的匹配的真字首子串和字尾子串的長度為k-1，那麼next[j+1]有以下兩種情況：

  (1)當T[j] = T[k]時，也就是說當T[j]失配的時候重新找到的匹配的位置與他相等，也就是說現在子串前k+1個字元相等，所以next[j+1]時，值為k+1，即next[j+1] = next[j] +1,一定要注意next值的定義。
  (2)當T[j] ！= T[k]時，這時候求next值的問題我們可以看作是一個模式匹配的問題，匹配的過程中模式串既是主串又是模式串。其中1<k’<k<j，相當於如果當前的失配，那麼就向前一直找直到下一位與當前主串的字元相匹配，或者直到子串的第一位還是不匹配，那麼主串和子串同時向後移動，這就是while迴圈的條件，具體如下:
  ①：若T[j] = T[k’],且k’ = next[k]，那麼next[j+1] = k’+1,即next[j+1] = next[next[k]]+1.
  ②：若T[j] ！= T[k]，則繼續比較T[j]和T[next[k’]]，即比較T[j]和T[next[next[k]]].
  然後一直這樣下去直到k = 0都沒有成功，則next[j+1] = 1.

next演演算法程式碼

void Get_Next(SString *T,int *next) {
	int i = 1, j = 0;
	next[1] = 0;
	while(i < T->len) {
		if(j == 0 || T->data[i] == T->data[j]) { //相等時，next的值等於j+1
			++i;
			++j;
			next[i] = j;
		} else {
			j = next[j];//往前尋找更小的匹配的子串
		}
	}
}

nextval演演算法的描述

  這是基於next的演演算法進行的，彌補next演演算法的缺陷的。
  主要解決了模式串中大量連續重複的字元，nextval函數減少了主串的無用比較的次數
  假設主串為：‘aaabaaaab’ 子串為:'aaaab’則對應的next函數值為下:
 

    j   1  2  3  4  5      模式串  a  a  a    a  b    next[j+1]  0  1  2  3  4   從匹配的過程中來說，如果已經和j = 4不匹配，那麼前面和T[j =4]相等的字元也無需比較了，直接去找下一位與其不同的字元即可。
  若 T[j] = T[next[j]],不需要進行S[i]和T[next[j]]的比較，直接進行S[i]和T[next[next[j]]]的比較,換句話說，此時的next[j] =next[k],將next[j]的值修正為nextval[j].
  若 T[j] != T[next[j]]的話，則當S[i] != T[j]時，還是需要進行S[i] 與 T[next[j]]的比較，因此nextval的值就是k. nextval演演算法程式碼

void Get_NextVal(SString *T, int *next, int *nextval)
{
	int j = 2;//j = 1時，nextval[1]的值預設為 0所以從2開始
	nextval[1] = 0;
	Get_Next( T, next);
	while(j <= T->len)
	{
		if(T->data[j] == T->data[next[j]])
		{
			nextval[j] = next[next[j]];
		}
		else{
			nextval[j] = next[j];
		}
		j++;
	}	
}