终结KMP算法

与KMP算法纠缠了好久,经历了难以理解->稍微开窍->明白也写不出来,的痛苦过程后,进行了一次详细的总结,来终结KMP算法。

参考文章https://www.zhihu.com/question/21923021/answer/281346746

朴素的模式匹配算法(Brute-Force算法)

说KMP算法之前,先看一下普通的字符串匹配算法,朴素的模式匹配算法就是是常规的匹配算法。
int find(char *s, char *t)
{
    int i = 0;  /*主串的位置*/
    int j = 0;  /*字串的位置*/
    while(i < strlen(s) && j < strlen(t))
    {
        if(s[i] == t[j])
        {
            i++;
            j++;
        }
        else
        {
            i = i - j + 1;      /*主串从下一个位置开始*/
            j = 0;
        }
    }
    if(j == strlen(t))      /*循环结束后如果模式串j的位置等于模式串长度,则匹配上了*/
        return i - strlen(t);
    else
        return -1;
}

什么是KMP算法

KMP是三位大牛:D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的。KMP算法是一种无回溯的模式匹配算法。
要理解KMP算法先来了解三个概念:前缀集合后缀集合PMT(部分匹配表)

前缀集合

如果字符串A和B,存在A=BS,其中S是任意的非空字符串,那么称B为A的前缀。
所有的前缀组成的集合,就是字符串的前缀集合。
例如:”Harry”的前缀包括{“H”,”Ha”,”Har”,”Harr”}

后缀集合

如果字符串A和B,存在A=SB,其中S是任意的非空字符串,那么称B为A的后缀。
所有的后缀组成的集合,就是字符串的后缀集合。
例如:”Potter”的后缀包括{“otter”,”tter”,”ter”,”er”,”r”}

部分匹配表(PMT)

有了如上的前缀后缀集合的定义后。PMT中的值的含义就是指:字符串的前缀集合与后缀集合的交集中最长元素的长度
例如:字符串”aba”
前缀集合为{"a","ab"}
后缀集合为{"ba","a"}
两个集合的交集为{"a"}
交集中最长元素的长度为1
所以对字符串"aba"而言,它在PMT表中对应的值就是1
在例如:字符串”ababa”
前缀集合为{"a","ab","aba","abab"}
后缀集合为{"baba","aba","ba","a"}
两个集合的交集为{"a","aba"}
所以对字符串"ababa"而言,它在PMT表中对应的值就是3
charabababca
index01234567
PMT00123401

PMT原理与使用

如下图所示,在主字符串”ababababca”中查找模式字符串”abababca”。

如果在j处字符不匹配,主字符串中i指针之前的PMT[j-1]位一定与模式串的第0位到j这一段是完全相同的。

模式串从0到j-1,在这个例子中就是”ababab”,该字符串的前缀集合与后缀集合的交集的最长元素为”abab”,长度为4。

则,主字符串中i指针之前的4位一定与模式字符串的0到4位是相同的,即长度为4的后缀与前缀相同。

则,可以省略掉这些字符段的比较,即,保持i指针不动,将j指针指向模式字符串的PMT[j-1]位。
 

next数组

如上所述,如果在j位失配,那么影响j指针回溯的位置的其实是第j-1位的PMT值。
为了编程方便,我们不直接使用PMT数组,而是将PMT数组向后偏移一位。新的到的数组就是next数组。再把PMT进行右移时,第0位置的值,设置为-1,只是为了编程方便。
charabababca
index01234567
PMT00123401
next-10012340

实现

KMP函数主体

int KMP(char *t, char *p, int next[])
{
    int i = 0;
    int j = 0;
    /***********************************************
    *strlen()返回的是无符号的整形,直接比较会出现错误。
    *next数组中存在-1。-1<strlen()实际返回假,我们期待真。
    ************************************************/
    while(i < (int)strlen(t) && j < (int)strlen(p))
    {
        if(j == -1 || t[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if(j == strlen(p))
        return i - j;
    else
        return -1;
}

编程求next数组

求next数组过程完全可以看成字符串匹配的过程,即以模式字符串为主字符串,以模式字符串的前缀为目标字符串,一旦字符串匹配成功,那么当前的next值就是匹配成功的字符串的长度。
void getNext(char *p, int *next)
{
    next[0] = -1;
    int i = 0;      /*主串位置*/
    int j = -1;     /*子串位置*/
    while(i < strlen(p))
    {
        if(j == -1 || p[i] == p[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
#if 1   /*调试打印*/
    for(j=0;j<i;j++)
    {
        printf("%d ",next[j]);
    }
    printf("\n");
#endif
}
/* unit test */
int main()
{
    char source[1024],target[100];
    int next[100];
    int ret=0;
    printf("please input source str:\n");
    scanf("%s",source);
    printf("please input target str:\n");
    scanf("%s",target);

    printf("target num next:\n");
    getNext(target,next);

    ret = KMP(source,target,next);
    if(ret==-1)
    {
        printf("no find tagret in source %d\n",ret);
    }
    else
    {
        printf("find tagret in source %d\n",ret);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据