大多數(shù)據(jù)結(jié)構(gòu)課本中，串涉及的內(nèi)容即串的模式匹配，需要掌握的是樸素算法、KMP算法及next值的求法。在考研備考中，參考嚴(yán)奶奶的教材，我也是在關(guān)于求next值的算法中卡了一下午時間，感覺挺有意思的，把一些思考的結(jié)果整理出來，與大家一起探討。

本文的邏輯順序為
1、最基本的樸素算法
2、優(yōu)化的KMP算法
3、應(yīng)算法需要定義的next值
4、手動寫出較短串的next值的方法
5、最難理解的、足足有5行的代碼的求next值的算法
所有鋪墊為了最后的第5點(diǎn)，我覺得以這個邏輯下來，由果索因還是相對好理解的，下面寫的很通俗，略顯不專業(yè)…

一、問題描述

給定一個主串S及一個模式串P，判斷模式串是否為主串的子串；若是，返回匹配的第一個元素的位置（序號從1開始），否則返回0；如S=“abcd”，P=“bcd”，則返回2；S=“abcd”，P=“acb”，返回0。

二、樸素算法

最簡單的方法及一次遍歷S與P。以S=“abcabaaaabaaacac”,P="abaabcac"為例，一張動圖模擬樸素算法：

這個算法簡單，不多說，附上代碼

#include<stdio.h>
int Index_1(char s[],int sLen,char p[],int pLen){//s為主串，sLen為主串元素個數(shù)，p為模式串，pLen為模式串的個數(shù)
    if(sLen<pLen)return 0;
    int i = 1,j = 1;
    while(i<=sLen && j<=pLen){
        if(s[i]==p[j]){i++;j++;}
        else{
            i = i-j+2;
            j = 1;
        }
    }
    if(j>pLen) return i-pLen;
    return 0;
}
void main(){
    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//從序號1開始存
    char p[]={' ','a','b','a','a','b','c','a','c'};
    int sLen = sizeof(s)/sizeof(char)-1;
    int pLen = sizeof(p)/sizeof(char)-1;
    printf("%d",Index_1(s,sLen,p,pLen));
}

三、改進(jìn)的算法——KMP算法

樸素算法理解簡單，但兩個串都有依次遍歷，時間復(fù)雜度為O(n*m)，效率不高。由此有了KMP算法。
一般的，在一次匹配中，我們是不知道主串的內(nèi)容的，而模式串是我們自己定義的。
樸素算法中，P的第j位失配，默認(rèn)的把P串后移一位。
但在前一輪的比較中，我們已經(jīng)知道了P的前(j-1)位與S中間對應(yīng)的某(j-1)個元素已經(jīng)匹配成功了。這就意味著，在一輪的嘗試匹配中，我們get到了主串的部分內(nèi)容，我們能否利用這些內(nèi)容，讓P多移幾位(我認(rèn)為這就是KMP算法最根本的東西)，減少遍歷的趟數(shù)呢？答案是肯定的。再看下面改進(jìn)后的動圖：

這個模擬過程即KMP算法，若沒有看明白，繼續(xù)往下看相應(yīng)的解釋，理解需要把P多移幾位，然后回頭再看一遍這個圖就很明了了。

相比樸素算法：
樸素算法： 每次失配，S串的索引i定位的本次嘗試匹配的第一個字符的后一個。P串的索引j定位到1；T(n)=O(n*m)
KMP算法： 每次失配，S串的索引i不動，P串的索引j定位到某個數(shù)。T(n)=O(n+m)，時間效率明顯提高

而這“定位到某個數(shù)”，這個數(shù)就是接下來引入的next值。（實際上也就是P往后移多少位，換一種說法罷了：從上圖中也可以看出，失配時固定i不變，令S[i]與P[某個數(shù)]對齊，實際上是P右移幾位的另一種表達(dá)，只有為什么這么表達(dá)，當(dāng)然是因為程序好寫。）

開——始——劃——重——點(diǎn)?。▓D對邏輯關(guān)系比較好理解，但i和j的關(guān)系對后面求next的算法好理解！）

• 比如，P_j處失配，綠色的是P_j，則我們可以確定P₁…P_j-1是與S_i…S_i+j-2相對應(yīng)的位置一一相等的
  

• 假設(shè)P₁…P_j-1中，P₁…P_k-1與P_j-k+1…P_j-1是一一相等的，為了下面說的清楚，把這種關(guān)系叫做“首尾重合”部分（這是我自己這樣叫的）
  

• 那么可以推出，P₁…P_k-1與S_i…S_i+j-2
  

• 顯然，接下來要做的就是把模式串右移了，移到哪里就不用多說了：
  

• 為了表示下一輪比較j定位的地方，我們將其定義為next[j]，next[j]就是第j個元素前j-1個元素首尾重合部分個數(shù)加一，當(dāng)然，為了能遍歷完整，首尾重合部分的元素個數(shù)應(yīng)取到最多，即next[j]應(yīng)取盡量大的值，原因挺好理解的，可以想個例子模擬一下，會完美跳過正確結(jié)果。在上圖中就是綠色元素的next值為藍(lán)色元素的序號。也即，對于字符串P，next[8]=4。如此，再看一下上面的動圖是不是清楚了不少。

• 最后，如果我們知道了一個字符串的next值，那么KMP算法也就很好懂了。相比樸素算法，當(dāng)發(fā)生失配時，i不變，j=next[j]就好啦！接下來就是怎么確定next值了。

四、手動寫出一個串的next值

我們規(guī)定任何一個串，next[1]=0。(不用next[0]，與串的所有對應(yīng))，仍是一張動圖搞定問題：

這個掃一眼就能依次寫出，會了這個方法，應(yīng)付個期末考試沒問題了。

通過把next值“看”出來，我們再來分析next值，這就很容易得到超級有名的公式了，這個式子對后面的算法理解很重要！所以先要看懂這個式子，如果上面的內(nèi)容通下來了，這個應(yīng)該很容易看懂了：

五、求next的算法

終于到了最后了~短的串的next值我們可以“看”出來，但長的串就需要借助程序了，具體算法剛接觸的時候確實不容易理解，但給我的體驗，把上面的內(nèi)容寫完，現(xiàn)在感覺簡簡單單了…先附上程序再做解釋，(終于到了傳說中的整整5行代碼讓我整理了一下午)。

int GetNext(char ch[],int cLen,int next[]){//cLen為串ch的長度
    next[1] = 0;
    int i = 1,j = 0;
    while(i<=cLen){
        if(j==0||ch[i]==ch[j]) next[++i] = ++j;
        else j = next[j];
    }
}

• 還是先由一般再推優(yōu)化：
  直接求next[j+1]（至于為什么是j+1，是為了和下面的對應(yīng)）
  根據(jù)之前的分析，next[j+1]的值為p_j+1的前j個元素的收尾重合的最大個數(shù)加一。即需要滿足兩個條件，把它的值一步步“檢驗”出來。一是“個數(shù)最多”的，因此要從可能的最大值開始驗；二是“首尾重合”，因此要一一對應(yīng)驗是否相等。
  不難理解，next[j+1]的最大值為j，所有我們從next[j+1]=j開始“驗證”。有以下優(yōu)先判斷順序：
  if(P₁…P_j-1 == P₂…P_j) => next[j+1]=j
  else if(P₁…P_j-2 == P₃…P_j) =>next[j+1]=j-1
  else if(P₁…P_j-3 == P₄…P_j) =>next[j+1]=j-2
  …
  …
  …
  else if(P₁P₂ == P_j-1P_j) => next[j+1]=3
  else if(P₁ == P_j-1) => next[j+1]=2
  else if(P₁ != P_j-1) => next[j+1]=1
  每次前去尾1個，后掐頭1個，直至得到next[j+1]

• 再進(jìn)一步想，next值是一個“工具”，我們單獨(dú)的求next[j+1]是完全沒有意義的，就是說要求next就要把所有j的next求出來。所有一般的，我們都是已知前j個元素的next值，求next[j+1]，以此遞推下去，求完整的next數(shù)組。
  但是，上面的思考過程還是最根本的。所以問題變?yōu)閮蓚€：知道前j個元素的next的情況下，
  ①next[j+1]的可能的最大值是多少（即從哪開始驗證）
  ②某一步驗證失敗后，需要“前去尾幾個，后掐頭幾個？”（即本次驗證失敗后，再驗證哪個值）
  看一下的分析：

1、next[j+1]的最大值為next[j]+1。
因為：
假設(shè)next[j]=k1，則可以說明P₁…P_k1-1=P_j-k1+1…P_j-1，且這是前j個元素最大的首尾重合序列。
如果P_k1=P_j，那么P₁…P_k1-1P_K=P_j-k1+1…P_j-1P_j，那么k+1這也是前j+1個元素的最大首尾重合序列，也即next[j+1]的值為k1+1
2、如果P_k1≠P_j，那么next[j+1]可能的次大值為next[next[j]]+1，以此類推即可高效求出next[j+1]
這里不好解釋，直接看下面的流程分析及圖解

開——始——劃——重——點(diǎn)！
從頭走一遍流程
①求next[j+1]，設(shè)值為m
②已知next[j]=k1，則有P₁…P_k1-1 = P_j-k1+1…P_j-1
③如果P_k1=P_j，則P₁…P_k1-1P_K = P_j-k1+1…P_j-1P_j，則next[j+1]=k1+1，否則
④已知next[k1]=k2，則有P₁…P_k2-1 = P_k1-k2+1…P_k1-1
⑤第二第三步聯(lián)合得到:
P₁…P_k2-1 = P_k1-k2+1…P_k1-1 = P_j-k1+1…P_k2-k1+j-1 = P_j-k2+1…P_j-1 即四段重合
⑥這時候，再判斷如果P_k2=P_j，則P₁…P_k2-1P~k2 = P_j-k2+1…P_j-1P_j，則next[j+1]=k2+1；否則再取next[k2]=k3…以此類推

上面幾步，耐心看下來，結(jié)合那個式子很容易看懂。最后，再加一個圖的模擬幫助理解：
1、要求next[k+1] 其中k+1=17

2、已知next[16]=8，則元素有以下關(guān)系：

3、如果P₈=P₁₆，則明顯next[17]=8+1=9
4、如果不相等，又若next[8]=4，則有以下關(guān)系

又加上2的條件知

主要是為了證明：

5、現(xiàn)在在判斷，如果P₁₆=P₄則next[17]=4+1=5，否則，在繼續(xù)遞推
6、若next[4]=1，則有以下關(guān)系

7、若P₁₆=P₂，則next[17]=1+1=2;否則繼續(xù)取next[2]=1、next[1]=0；遇到0時還沒出結(jié)果，則遞推結(jié)束，此時next[17]=1。最后，再返回看那5行算法，應(yīng)該很容易明白了！