详解KMP算法 另一种思路

这个算法单纯从代码理解起来比较费劲.我觉得从思路上理解是非常简单的.

传统算法的劣势很容易察觉.那就是会有重复的匹配过程.我们假定 Text为待查文本, Pattern 为匹配串.

Text="aaaaB"

Pattern="aB"

按以下传统算法.则直到循环到最后一次比较.才找到"aB".而前面很多循环都是做的无用功.

 

#include <stdio.h>
#include <string.h>
typedef const char* const CSTR;
int findStr(CSTR src,int from,CSTR des)
{
    const char* p=src+from;

    while (*p)
    {
        const char* pStr1=p;
        const char* pDes=des;
        while (*pStr1 && *pStr1 == *pDes )
        {
            pDes++;
            pStr1++;
            if(!*pDes )  
                return (pStr1-src-(pDes - des))/sizeof(char) ;
        }
        p++;
    }
    return -1;
}

 

而kmp算法是想怎么思考的呢?

是这样.让Pattern字符串里的每一个字符都带上一个标示.来标示Pattern字符之间的关系.这些字符间的关系可以省下很多重复的比较.比如说

如果Pattern="ABCABCABC"   Text="ABCABX"

模拟计算机比较过程,请把下面的字符串看成可左右移动的纸带.

黑体表示从左到右的比较,并相等.红色代表不相等发生处,维护两个下标.代表当前对比的字符串.我就不取名字了.免得你头晕.用彩色表示.此处为红色.

 

ABCABCABC   

ABCABX

 

当计算到C与X不相等时.计算机该怎么做才最有效率呢?? 传统算法会这样,将Text的对比下标指向B.

 

ABCABCABC

 ABCABX

 

KMP会怎样?KMP会这样...

 

ABCABCABC

      ABCABX

所以KMP诡异在哪? 它为什么要跳过去.为什么要从Pattern[2]开始比较??而不是从头开始比较?  其实道理非常简单,我们先回到刚开始比较时候的情况

 

ABCABCABC   

ABCABX

 

再具体看看Pattern

ABCABX      我将AB标蓝.而且加了下划线.为什么?因为他们是重复的!!!并且是与开头的串重复.!! 这种重复有什么性质呢?我们把开头的AB称为第一组.后面的AB为第二组.

 

ABCABCABC   

ABCABX

 

如果在对比完第二组AB后,当C与X对比发现了不相同时.由于第一组AB与第二组AB是相同的, 在Text[5]与Pattern[5]对比不相同后,将第1组AB的位置替换第二组AB的位置.再进行下一个字符的比较. 上面示例的和下面示例的转换是对等的.而下面的下一步将是比较Text[5]与Pattern[2] 也即 也即比较C 与 C. 相等.  特别要注意的是Text下标在下一轮比较中下标未动.(橙色代表将要比较的字符,但还没比较 )

 

ABCABCABC   

      ABCABX

 

如果你看到,并理解了.其实你已经懂了KMP的核心思想了.只不过要将这个思想再具体化而已了.

首先要解决的一问题.我怎么知道在发现C与X不等时,让Pattern哪一位再来与C比较呢?从上面的示例可以看出.是Pattern[2].好.我们已经解决了一个问题了.那我们把2存哪呢??既然它与Pattern[5]相关,也即与X相关.我们建一个与Pattern一样长度的int数组.名叫Next[],指定Next[5]=2.

 

ABCABCABC   

ABCABX

 

第二个问题随即而来,Next数组其他的数值填什么呢? 我们先想另外一个问题.那就是.我们什么时候会需要Next里的值?对了.那就是当Pattern与Text 在对比某值发生了不相等的时候.比如上面的C跟X.现在我们将Text改一下,Pattern保持不变,不然Next其他值用不到,KMP算法就结束了...:) 变成如下,

ABCBDCABC   

ABCABX

当对比到Text[3]与 Pattern[3]时,发现了不同. 这个时候怎么移动Pattern呢? 很简单.如果你看出了规律! 请按你规律写算法即可.而我....太蠢没看出规律..所以.在Next[3]处.我将填入一个 -1 ,意思是, Pattern回到起点开始比较.而Text往后移一位.如下示..哦.为什么要移一位?? 首先我请问你一个问题.

ABCBDCABC  

       ABCABX

 

那就是,随你怎么改Text串.你能得到某个Text串使前面提到的移一位会出现错误吗?你会发现..永远不会..为啥 ? 我们来看一下Pattern串. 其中重复的AB.A为重复串的开头.这个信息看起来有点重要..的确如此.看上面Text[3]与Pattern[3]不等.在而Pattern[3]是一个特殊的值..它是重复串AB的第一个值.所以如果像下面所示.有意义么...?没有!! 肯定不等.(而且在算法里会产生死循环...动不了了...) 好了,我们现在又有了一个规则.重复串的开关必须为 -1 . 现在Next值又多了两个成员Next[0]= -1, Next[3] =-1; 再有一个Next[5] =2.在上文已提过.

ABCBDCABC  

      ABCABX

 

现在Next数组已经填了3个数了.貌似还剩下3个没填..怎么办!!  其实.很简单.如果你觉得没有再可以优化的地方了.你就直接调用传统查找算法.而核心思想就是Pattern 回到 0 位置.Text保持不动.至于怎么在Next里表示.那随你.~按我们现在的逻辑最好是写个0.代表回到Pattern[0].这样最好.但记住.还要保持Text别动.不是像 Next[k]=-1一样.向后移一位.

 

所以我们看看Next这个数组...是个什么东西?其实就是一个对Pattern规律的一个表示形式而已.我上面描述的规律还只总结了两条而已.你可以总结更多条,在算法中加已利用.我们总结了哪两条规则?

    ABEEEABFABF  我们就拿这个做例子.我不喜欢说定理...一堆j k 参数看着头晕 ..

ABEEEABFABF   开头的重复与后面的重复找出来.将Next[0]=-1.将Next[5]=-1;将Next[8]=-1 ,将Next[7]=2 将Next[10]=2;  Next其他的值填为0.

则得到.

Next[]={-1, 0, 0, 0, 0, -1, 0, 2, -1, 0, 2};

少年.你学会KMP了...你可以发挥你的才能继续扩展KMP.因为0放在那有些浪费 ....

 

给一个规则更多的求next的 函数 看它的if大概能猜到有4条规则..你可以想更多.

 

 

void  genPattern(const char* const  des,int ** pattern, int* size )
{
    *size=strlen(des);
    (*pattern)=new int[*size];

    (*pattern)[0]=0;

    int j=1;
    int start=0;
    int same_from_beg=0;
    bool after_repeat_char=false;
    while (*(des+j))
    {
        if(  after_repeat_char) start++;
        else start=0;
        if (*(des+j)==*(des+start))
        {
            (*pattern)[j]=0 ;
            same_from_beg++;
            if(*(des+j)==*(des))
                after_repeat_char=false;
            else
                after_repeat_char=true;

        }else
        {
            if(after_repeat_char)
                (*pattern)[j]=same_from_beg;
            else
                (*pattern)[j]=-1;

        }
        j++;

    }  



}

 

 

 

再提供一个与之配套的KMP算法 ,将代码复制。自己跑跑，有可视化的console打印

 

int kmp(const char* src,const char * des )
{
    const char* p=src ;
    int * pattern, size,i=0, j=0;

    genPattern(des,&pattern,&size);

    while(*(p+i)  ) 
    {
        //debug print
        {
            printf("%s\n",src);
            for (int a=0;a<i-j;a++)
            {
                printf(" ");
            }
            for (int a=0;a< j+1;a++)
            {

                if(a ==j && *(p+i) != *(des+j))

                    printf("*");
                else
                    printf("|");

            }
            printf("\n");
            for (int a=0;a<i-j;a++)
            {
                printf(" ");
            }
            printf("%s\n\n",des);
        }

        if(*(p+i) != *(des+j))
        {
            if(pattern[j]==0)
            {
                i++;
                j=0;
            }else if(pattern[j]==-1)
            {
                j=0;
            }else
            {
                j=pattern[j];
            } 
        }else
        {
            i++;
            j++;
            if( j==size)  //found
                return 1;
        }

    }


    return -1;
}

 

免费供应一个main函数 :)

int main()
{
char* text="abcabcabcx";
char*pattern="abcx";
cout<<KMP(text,pattern)<<endl;
return 0;
}

---console------------

abcabcx
|
abcx

abcabcx
||
abcx

abcabcx
|||
abcx

abcabcx
|||*
abcx

abcabcx
   |
   abcx

abcabcx
   ||
   abcx

abcabcx
   |||
   abcx

abcabcx
   ||||
   abcx