专栏首页饶文津的专栏模式匹配KMP算法

模式匹配KMP算法

关于KMP算法的原理网上有很详细的解释,我试着总结理解一下:

KMP算法是什么

  以这张图片为例子

  匹配到j=5时失效了,BF算法里我们会使i=1,j=0,再看s的第i位开始能不能匹配,而KMP算法接下来就去比较T[2](next[5]=2)和S[5]

next数组什么意思?

就是当t[i]不匹配时,就让i=next[i]再去比较,则t[next[i]]前面的部分和s[j]前面一定是相同的,因为t[next[i]]前面的部分和t[i]前面的部分是相同的,图中相同颜色代表字符串相同部分。也就是我们利用模式串的自身匹配的特点,来减少和目标串的比较。

next数组怎么算?

我们算好next[i],去算next[i+1]时分两种情况:

  • T[i]==T[k] (k=next[i]) 时,next[i+1]=k+1。
  • T[i]!=T[k] 时,先看图左,在匹配的部分里(灰色)有更小的一段(蓝色),是next[next[i]]前面的子串,根据next数组的含义,蓝色的和粉色的子串相同,因为两段灰色是相同的,那左蓝就和右粉相同,
  • 如果这时Ti=Tnext[k],那next[i+1]就是next[k]+1,否则继续找更小的一段,直到k=-1,那么next[i]=0。
void get_next(const string &T,int *next){
    int i=0,k=-1;
    next[i]=k;
    while(T[i]){
        if(k==-1||T[k]==T[i])
        {
            ++k;
            ++i;
            next[i]=k;
        }else{
            k=next[k];
        }
    }
}

但是其实还可以再改进

  上面算next[i+1]时不考虑T[i+1]是什么,T[i]失配,用T[next[i]]去比较,可以保证T[next[i]]前面的都能匹配,但是如果T[next[i]]==T[i],跳到next[i]肯定还是失配,所以算next时要考虑一下T[next[i]]和T[i]是否相等。

算好next[i],去算next[i+1]时:

如果 T[k]==T[i]且T[i+1]==T[k+1],由于T[i+1]失配了,T[k+1]肯定也会失配,那next[i+1]应该继续跳到next[k+1]。

改进后的next计算代码:

void get_next()
{
    int i=0,k=-1;
    next[i]=k;
    while(T[i])
    {
        if(k==-1||T[i]==T[k])
        {
            ++k;
            ++i;
            if(T[i] == T[k])
                next[i] = next[k];
            else
                next[i] = k;
        }
        else
            k=next[k];
    }
}

另一种get_next的写法

void get_next()
{
    int i,k=-1;
    next[0]=k;
    for(i=1;T[i];i++){
        while(k>=0 && T[k+1]!=T[i]) k=next[k];
        if (T[k+1]==T[i]) k++;
        next[i]=k;
    }
}

完整程序代码:

#include<iostream>
#include<cstring>
const int N = 1005;

int next[N];
char T[N],S[N];

void get_next()
{
    int i=0,k=-1;
    next[i]=k;
    while(T[i]){
        if(k==-1||T[i]==T[k]){
            ++i;
            ++k;
            if(T[i]==T[k])
                next[i]=next[k];
            else
                next[i]=k;
        }else{
            k=next[k];
        }
    }
}

int KMP()
{
    int i=0,j=0;
    while(S[j]&&(i==-1||T[i])){
        if(i==-1||S[j]==T[i]){
            ++i;
            ++j;
        }else{
            i=next[i];
        }
    }
    if(!T[i])return j-i;
    return -1;
}

int main(){
    std::cin>>T>>S;
    get_next();
    std::cout<<KMP()+1<<std::endl;
    return 0;
}
/*
abcaccdacb
abcaccdaccccaccabcaccdaccacabcaccdacb
输出28
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【HDU 3746】Simpsons’ Hidden Talents(KMP求循环节)

    饶文津
  • 【ZOJ2277】The Gate to Freedom

    饶文津
  • 【计导作业】链表——差集与交集

    问题描述:已知有两个递增的正整数序列A和B,序列中元素个数未知,同一序列中不会有重复元素出现,有可能某个序列为空。你的任务是求这两个序列的差集A-B与交集A+B...

    饶文津
  • leetcode:83 删除排序链表中的重复元素

    问题? 如果next没有值的话,会报错的。 因为要相等啊,比较啊,有值才能比较是吧。 那为什么p.next=p.next.next;如果p.next.ne...

    用户7873631
  • 【玩转腾讯云】python next函数

    python 3.x内置函数next可以从迭代器中检索下一个元素或者数据,可以用于迭代器遍历,使用的时候注意会触发 StopIteration 异常!

    猿说编程[Python和C]
  • c/c++补完计划(七): 哨兵节点

    sean_yang
  • leetcode: 206. Reverse Linked List

    JNingWei
  • 吃透洋葱模型

    作者:掘金@苏里 https://juejin.im/post/6844904025767280648

    zz_jesse
  • leetcode: 86. Partition List

    JNingWei
  • 【力扣】_92反转链表II

    瑞新

扫码关注云+社区

领取腾讯云代金券