快捷導(dǎo)航

C語言kmp算法簡單示例和實(shí)現(xiàn)原理探究

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

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

以前看過kmp算法，當(dāng)時(shí)接觸后總感覺好深?yuàn)W啊，抱著數(shù)據(jù)結(jié)構(gòu)的數(shù)啃了一中午，最終才大致看懂，后來提起kmp也只剩下“奧，它是做模式匹配的”這點(diǎn)干貨。最近有空，翻出來算法導(dǎo)論看看，原來就是這么簡單（下不說程序?qū)崿F(xiàn)，思想很簡單）。

模式匹配的經(jīng)典應(yīng)用：從一個(gè)字符串中找到模式字串的位置。如“abcdef”中“cde”出現(xiàn)在原串第三個(gè)位置。從基礎(chǔ)看起

樸素的模式匹配算法

A：abcdefg B：cde

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

復(fù)制代碼代碼如下:

/*
*侯凱,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");
}

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

kmp算法

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

再比如：

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

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

j是前一次執(zhí)行的模式子串（前幾個(gè)，上例為6）中前綴的個(gè)數(shù)+1；它與模式字串中從前向后的前綴和從后向前的后綴的相同子串是有關(guān)系的，因?yàn)橄麓芜@部分相同的前綴就會(huì)移動(dòng)到這部分后綴的位置，因?yàn)槿绻苿?dòng)到后綴的前面位置，看圖：

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

這次是j，下次到底是多少呢，這就涉及到怎么計(jì)算的問題了？其實(shí)只看模式串我們就可以構(gòu)建出這個(gè)j->x的關(guān)系，關(guān)系稱為前綴函數(shù)，結(jié)果存儲(chǔ)在數(shù)組中，稱為前綴數(shù)組。

偽代碼：

復(fù)制代碼代碼如下:

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

使用前綴數(shù)組可很快地實(shí)現(xiàn)模式匹配，程序匹配字符串中模式出現(xiàn)的所有位置。

復(fù)制代碼代碼如下:

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有難理解的地方，估計(jì)就是這段偽碼的了。

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

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

您可能感興趣的文章: