kmp算法研究

    這段時間在看關于kmp算法的内容，其中尤其是matrix67大牛的那篇kmp算法詳解，網上評價很高。說實話一開始看沒怎麼看懂，後面主要結合代碼仔細跟了跟， 思路清晰了很多。kmp算法的關鍵在于利用字元串自身的特點在一處不能比對後大幅移動，進而将效率降為線性的。

    此文并不是從頭講kmp的原理等東西，隻是說說自己的一些想法。如果對于kmp想要從頭了解的話，可以參考matrix67大牛和網上其他大牛的著作。

    kmp的關鍵在于，預處理 存放當不能比對時下一個比對位置的數組。也就是自我比對的過程，其中P[j]應該是所有滿足B[1..P[j]]=B[j-P[j]+1..j]的最大值。

    matrix67大牛的代碼是

P[1]:=0;
j:=0;
for i:=2 to m do
begin
   while (j>0) and (B[j+1]<>B[i]) do j:=P[j];
   if B[j+1]=B[i] then j:=j+1;
   P[i]:=j;
end;
           

這是Pascal的代碼，将其改成C的便是

dst[0] = -1;
j = -1;
for (i = 1; i < strlen(src); i++)
{
    while ((j > -1) && (src[j + 1] != src[i]))
    {
        j = dst[j];
    }
    if (src[j+ 1] == src[i])
    {
        j++;
    }
    dst[i] = j;
}
           

中間稍作了些處理

如果輸入為：

char src[] = "abababacaba";
           

運作結果為：

src[]:  a  b  a  b  a  b  a  c  a  b  a 
dst[]: -1 -1  0  1  2  3  4 -1  0  1  2 
           

但是中間的-1，0會讓人很暈。其實都是需要從頭比對的意思，均可以改成零，這樣可以更好得了解。

自己寫了個函數可以更友善的用

void kmp_get_next(const char *src, int *dst)
{
    int i, j, len_src;
    dst[0] = 0;
    j = 0;
    len_src = strlen(src);

    for (i = 1; i < len_src; i++)
    {
        while ((j > 0) && (src[j] != src[i]))
        {
            j = dst[j];
        }
        dst[i] = j;
        if (src[j] == src[i])
        {
            j++;
        }
        
    }
    return ;
}
           

運作結果為

src[]: a  b  a  b  a  b  a  c  a  b  a 
dst[]: 0  0  0  1  2  3  4  0  0  1  2 
           

當然，最終的kmp比對的函數也需要相應修改

int kmp_matching(const char *dst,       //待檢查的字元串
                 const char *match_str, //比對字元串
                 int *match_arr         //預處理數組
                )
{
    int count = 0;                      //計數，比對成功次數
    int i, j = 0;
    int len_dst = strlen(dst);
    int len_match = strlen(match_str);

    for (i = 0; i < len_dst; i++)
    {
        while ((j > 0) && (dst[i] != match_str[j]))
        {
            j = match_arr[j];
        }
        if (dst[i] == match_str[j])
        {
            j++;
        }

        if (j == len_match)
        {
            printf("one matching at %d\n", i - len_match + 1);
            j = match_arr[j];
            count++;
        }
    }
    if (count == 0)
    {
        printf("no matching\n");
    }
    return count;
}
           

此外，生成的預處理數組空間還可以用malloc的方式動态開辟。将這兩個函數一封裝，就可以成為一個子產品了。

總的來說，整體的思想沒變，隻是對其中稍作修改，便于自己深入了解而已

轉貼請注明出處