串（string）的模式比對算法（KMP算法）

簡單模式比對算法

int index(Str str,Str substr)
{
    int i=1,j=1,k=i;
    while(i<=str.length && j<=substr.length)
    {
        if (str.ch[i]==substr.ch[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j=1;
            i=++k;
        }
    }
    if (j>substr.length)
        return k;
    else
        return 0;
}
           

KMP算法

一般情況：每當發生不比對時，找出模式串中的不比對字元

，取其之前的子串 

,将模式串後移，使F最先發生前部與後部相重合的位置，即為模式串應後移的目标位置。    事實上，在計算機中模式串是不會移動的，是以需要把模式串後移轉化為 j 的變化，模式串後後移到某個位置可等效于 j 重新指向某個位置。易看出，j發生不比對時，j 重新指向的位置恰好是F串中前後相重合子串的長度+1.      定義一個next[j]數組，其中 j 取1~m，m為模式串長度，表示模式串中第 j 個字元發生不比對時，應從next[j]處的字元開始重新與主串比較。

特殊情況：

1）模式串中的第一個字元與主串 i 位置不比對，應從（主串）下一個位置（i+1位置）和模串第一個字元繼續比較。

2）當串F中不存在前後重合部分時（F與自身不能視為重合），則從主串中發生不比對的字元與模式串第一個字元開始比較。

next[j]數組的手工求解方法

 直接跳到 

 就是通常所說的簡單模式比對算法中 i 不需要回溯。i 不需要回溯意味着對于規模較大的外存中字元串的比對操作可以分段進行，先讀入記憶體一部分進行比對，完成之後即可寫會外存，確定在發生不比對時不需要将之前寫回外存的部分再次讀入，減少了I/O操作，提高了效率。

next[j]的值已經求得，則next[j+1]的求值可分為兩種情況分析

1）若

 等于

，則next[j+1]=t+1，因為 t 目前為F最長相等前字尾長度

2）若 

 不等于

，隻需将 t 值指派為next[t],繼續進行 

 與 

 的比較，若滿足1）則求得next[j+1]，不滿足則重複 t 指派為next[t]，并比較 

 與 

 的過程。若在這個過程中 t 出現0的情況，則應将next[j+1]指派為1.

/*求next數組的算法*/
void getnext(Str substr,int next[])
{
    int i=1,j=0;
    next[1]=0;  //
    while(i<substr.length)
    {
        if (j==0||substr.ch[i]==substr.ch[j])
        {
            ++i;
            ++j;
            next[i]=j;
        }
        else
            j=next[j];
    }
}
           

得到next數組之後，将簡單模式比對算法稍作修改就可以得到狀态從 

 到 

 的改進算法

/*KMP算法*/
int KMP(Str str,Str substr，int next[])
{
    int i=1,j=1;
    while(i<=str.length && j<=substr.length)
    {
        if (str.ch[i]==substr.ch[j])
        {
            ++i;
            ++j;
        }
        else
            j=next[j];
    }
    if (j>substr.length)
        return i-substr.length;
    else
        return 0;
}
           

KMP算法的改進

求nextval的一般步驟：

1）當 j 等于1 時，nextval[j]指派為0，作為特殊标記。

2）當 

 不等于 

 時（k等于next[j]），nextval[j]指派為k。

3）當 

 等于 

 時（k等于next[j]），nextval[j]指派為nextval[k]。

/*求nextval數組的算法*/
void getnextval(Str substr,int nextval[])
{
    int i=1,j=0;
    nextval[1]=0;  //
    while(i<substr.length)
    {
        if (j==0||substr.ch[i]==substr.ch[j])
        {
            ++i;
            ++j;
            if (substr.ch[i]!=substr.ch[j])
                nextval[i]=j;
            else
                nextval[i]=nextval[j]
        }
        else
            j=nextval[j];
    }
}