C語言kmp算法簡單示例和實現原理探究

更新時間：2014年09月24日 10:53:51 投稿：junjie

這篇文章主要介紹了C語言kmp算法簡單示例和實現原理探究,本文用簡潔的語言說明KMP算法的原理,并給出了示例,需要的朋友可以參考下

以前看過kmp算法，當時接觸后總感覺好深奧啊，抱著數據結構的數啃了一中午，最終才大致看懂，后來提起kmp也只剩下“奧，它是做模式匹配的”這點干貨。最近有空，翻出來算法導論看看，原來就是這么簡單（下不說程序實現，思想很簡單）。

模式匹配的經典應用：從一個字符串中找到模式字串的位置。如“abcdef”中“cde”出現在原串第三個位置。從基礎看起

樸素的模式匹配算法

A：abcdefg B：cde

首先B從A的第一位開始比較，B++==A++，如果全部成立，返回即可；如果不成立，跳出，從A的第二位開始比較，以此類推。

復制代碼代碼如下:

/*
*侯凱,2014-9-16
*功能：模式匹配
*/
#include<iostream>
#include <string>
using namespace std;

int index(char *a,char *b)
{
    int tarindex = 0;
    while(a[tarindex]!='\0')
    {
        int tarlen = tarindex;
        int patlen;
        for(patlen=0;b[patlen]!='\0';patlen++)
        {
            if(a[tarlen++]!=b[patlen])
            {
                break;
            }
        }
        if(b[patlen]=='\0')
        {
            return tarindex;
        }
        tarindex++;
    }
    return -1;
}
int main()
{
    char *a = "abcdef";
    char *b = "cdf";
    cout<<index(a,b)<<endl;
      system("Pause");
}

思路樸實無華，十分有效，但是時間復雜度是O(mn)，m、n分別是字符串和模式串的長度。模式匹配是一個常見的應用問題，用的廣了，就有人想法去優(yōu)化了。Rabin-Karp算法、有限自動機等等，前仆后繼，最終出現了KMP(Knuth-Morris-Pratt)算法。

kmp算法

優(yōu)化的地方：如果我們知道模式中a和后面的是不相等的，那么第一次比較后，發(fā)現后面的的4個字符均對應相等，可見a下次匹配的位置可以直接定位到f了。說明主串對應位置i的回溯是不必要的。這是kmp最基本最關鍵的思想和目標。

再比如：

由于abc 與后面的abc相等，可以直接得到紅色的部分。而且根據前一次比較的結果，abc就不需要比較了，現在只需從f-a處開始比較即可。說明主串對應位置i的回溯是不必要的。要變化的是模式串中j的位置（j不一定是從1開始的，比如第二個例子）

j的變化取決于模式串的前后綴的相似度，例2中abc和abc（靠近x的），前綴為abc，j=4開始執(zhí)行。

j是前一次執(zhí)行的模式子串（前幾個，上例為6）中前綴的個數+1；它與模式字串中從前向后的前綴和從后向前的后綴的相同子串是有關系的，因為下次這部分相同的前綴就會移動到這部分后綴的位置，因為如果移動到后綴的前面位置，看圖：

所以如果這次是j，下次的位置應該就是j前面的子串的最大前綴的長度+1,用這個新的位置再和原字符串的i位置進行比較就很幸福了。

這次是j，下次到底是多少呢，這就涉及到怎么計算的問題了？其實只看模式串我們就可以構建出這個j->x的關系，關系稱為前綴函數，結果存儲在數組中，稱為前綴數組。

偽代碼：

復制代碼代碼如下:

compiter-prefix-function(P)

    m<-length[p]

    pi[1]<-0

    k<-0

    for q<-2 to m

        do while k>0 and P[k+1]!=P[q]

                    do k<-pi[k] //前綴的前綴...

           if P[k+1]==P[q]

                    then k<-k+1

           pi[q]<-k

    return pi

使用前綴數組可很快地實現模式匹配，程序匹配字符串中模式出現的所有位置。

復制代碼代碼如下:

kmp-matcher(T, P)

    n<-length[T]

    m<-length[P]

    pi<-compiter-prefix-function(P)

    q<-0

    for i<-1 to n

        do while q>0 and P[q+1]!=T[i]

            do q<-pi[q] //前綴的前綴...

        if P[q+1]==T[i]

            then q<-q+1

        if q==m

            then print “Pattern occurs with shift”i-m

                    q<-pi[q]

這兩段代碼思想完全相同,如果和前綴不同就比較前綴的前綴…，比較巧妙。如果kmp有難理解的地方，估計就是這段偽碼的了。

KMP算法的時間復雜度為O(n+m)。

這里需要強調一下，KMP算法的僅當模式與主串之間存在很多部分匹配情況下才能體現它的優(yōu)勢，部分匹配時KMP的i不需要回溯，否則和樸素模式匹配沒有什么差別。

您可能感興趣的文章: