学习笔记 编程与算法

磨人的KMP算法

之所以说KMP磨人是因为,他真的不怎么好懂,就算懂了,也不怎么好写0.0也有可能是我太菜了

KMP算法就是为了应对暴力匹配字符串带来的庞大的消耗,总的来说就是在匹配字符串的过程中如果发生匹配失败,不采用暴力匹配的方法直接从当前字符串的下一个位置开始匹配,而是最大程度的把匹配串向右移动尽可能多的字符。当然这里的移动并不是随便移动,而是根据一个移动表格(next数组)来进行移动

暴力匹配的思想就是逐个匹配,但是这是KMP怎么会这么low,当然对于下面这个字符串,刚开始可能和暴力匹配差不多

BBC ABCDAB ABCDABCDABDE

ABCDABD

依旧不相等,继续整体后移

BBC ABCDAB ABCDABCDABDE

#ABCDABD

整体移动到下面位置时,匹配成功一个字符

BBC ABCDAB ABCDABCDABDE

### ABCDABD

然后匹配一次对后面的字符进行匹配

BBC ABCDAB ABCDABCDABDE

### ABCDABD

到这个位置匹配失败,按照暴力匹配的方法应该将匹配串的头和目标串的第6个字符进行比较,但是根据KMP的思想,应该在出现错误的基础上,最大限度的右移匹配串

BBC ABCDAB ABCDABCDABDE

### ABCDABD

然后根据之前构造好的Next表(后续会说明Next表的原理),在D位置匹配失败,然后匹配成功的最后一个字符是B,B对应的Next数组值为2,这个时候我们就应该将字符串后移:(已经匹配的字符个数-部分匹配值)个字符

ABCDABD

000012

因为已经匹配的字符数是6,部分匹配值是2,所以得出字符串向后移动4个单位

BBC ABCDAB ABCDABCDABDE

### ####ABCDABD

然后按照常规的匹配的规则继续匹配,直到出现下图的情况。再按照KMP的处理方法,尽可能的后移匹配串,知道匹配成

BBC ABCDAB ABCDABCDABDE

### ####ABCDABD

到这里都好懂,然后就开始想这个Next数组是怎么求出来的?然后我就懵逼在Next数组上

说到这了都,问题就演变成了如何求Next数组的部分匹配值了。网上其他的博客上还引入了前缀和后缀的概念,但是我认为没有什么必要。所谓的部分匹配值就是,从头开始对匹配串进行重复查找,简单的来说A B C D A B D,1-4的部分匹配值为0,但是5-6出现了重复组A B,第7位虽然也在前面出现,但是组A B D没有在前面出现,所以D位置的部分匹配值为0

OK,原理大概就是这样,剩下的一个问题就是代码了

其实整体很难解决的就是一个Next数组的构造和KMP的主程序

根据上面的原理实际上Next数组就很好实现了

void setNext(const char P[],int next[])
{
    int q,k;//q:模版字符串下标;k:最大前后缀长度
    int m = strlen(P);
    next[0] = 0;
    for (q = 1,k = 0; q < m; ++q)
    {
        while(k > 0 && P[q] != P[k])
            k = next[k-1];        
        if (P[q] == P[k])
        {
            k++;
        }
        next[q] = k;
    }
}

既然有了Next数组,那就可以很愉快的写KMP函数了

int kmp(const char T[],const char P[],int next[])
{
    int n,m;
    int i,q;
    n = strlen(T);
    m = strlen(P);
    setNext(P,next);
    for (i = 0,q = 0; i < n; ++i)
    {
        while(q > 0 && P[q] != T[i])
            q = next[q-1];
        if (P[q] == T[i])
        {
            q++;
        }
        if (q == m)
        {
            printf("匹配串开始的位置是:%d\n",(i-m+1));
        }
    }    
}

这么看的话磨人的KMP算法其实也不是很难

发表评论

您的电子邮箱地址不会被公开。