首页 / 算法 / 模式匹配KMP算法

模式匹配KMP算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了模式匹配KMP算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2327字，纯文字阅读大概需要4分钟。

内容图文

关于KMP算法的原理网上有很详细的解释，我总结一下理解它的要点：

　　以这张图片为例子

技术分享

　　这里我们匹配到j=5时失效了，接下来就直接比较T[2]（next[5]=2）和S[5]

那为什么可以跳过朴素算法里的几次比较，而直接用T[next[j]]比较就可以呢？

  • 我们匹配过S0S1S2S3S4=T0T1T2T3T4，
  • next[5]=2,2是公共序列的最大长度了，也就是说:
  • T0T1=T3T4,但是T0T1T2≠T2T3T4，T0T1T2T3≠T1T2T3T4，
  • 那么就有S3S4=T3T4=T0T1，而S2S3S4=T2T3T4≠T0T1T2，S1S2S3S4=T1T2T3T4≠T0T1T2T3
  • 所以可以直接比较T2和S5

　　Q：next数组计算的原理是什么？

技术分享

　　如果我们算完了next[i] ，现在要算next[i+1]了，我们让k=next[i]，

  • 可以看到如果 k 和 i 位置的字符相同（T[i]和T[k]比较了,i,k再增加1，因为如果k和i位置的字符不同的话，k和i还不能增加1，见下文分析），那next[i+1]就等于k+1，代码就是：
if(T[k]==T[i])
    {   
        k++;
        i++;
        next[i]=k;
    }
  • 如果不同呢？那就有next[i+1]≤next[i]，不可能有更长的公共序列，
  • 而在匹配的部分里（图中灰色）有更小的一段（图中蓝色部分），是next[next[i]]前面的子串，根据next数组的含义，左右的蓝色的和粉色的子串分别相同，因为左右灰色部分是相同的，那左边的蓝色就和右边的粉色相同，
  • 如果这时Ti=Tnext[k]，那它就是next[i]的值了，否则继续找更小的一段（这一部分和上面的判断是差不多的，所以只要更新k=next[k]，然后继续循环就可以了），直到k=-1，那么next[i]就等于-1了，

整个的代码就是：

void get_next(const string &T,int *next){
    int i=0,k=-1;
    next[i]=k;
    while(T[i]!=‘\0‘){
        if(k==-1||T[k]==T[i])
        {
            k++;
            i++;
            next[i]=k;
        }else{
            k=next[k];
        }
    }
}

　　但是其实还可以再改进，因为例如

技术分享

　　那么当i=3失配时，T的移动如下，

技术分享

　　这样没有利用前面那么多a一样的特点，导致匹配次数比较多，所以我们这样改进：

　　因为T[3]失配了，而T[3]=T[2]，所以T[2]也会失配，因为失配，所以还要用next寻找合适的匹配位置，所以next[3]=next[2]。在我们计算next[3]之前，next[2]已经计算出来，同理的，next[2]=next[1]=next[0]=-1。

　　所以改进的next的规则多了一条：

　如果T[i]=T[i-1],next[i]=next[i-1]

　　在这里，next[0]=-1,next[1]=-1,next[2]=-1,next[3]=-1,next[4]=3,代码就变成了：

void get_next(const string &T,int *next)
{
    int i=0,k=-1;
    next[i]=k;
    while(T[i]!=‘\0‘)
    {
        if(k==-1||T[k]==T[i])
        {
            k++;
            i++;
            if(T[i] != T[k])
                next[i] = k;
            else
                next[i] = next[k];
        }
        else
        {
            k=next[k];
        }
    }
}

　　完整程序代码：

#include<iostream>
#include<cstring>
using namespace std;
void get_next(const string &T,int *next)
{
    int i=0,k=-1;
    next[i]=k;
    while(T[i]!=‘\0‘)
    {
        if(k==-1||T[k]==T[i])
        {
            k++;
            i++;
            if(T[i] != T[k])
                next[i] = k;
            else
                next[i] = next[k];
        }
        else
            k=next[k];
    }
}
/*
返回模式串T在主串P的第pos个字符起第一次出现的位置，
若不存在，则返回-1，下标从0开始，0<=pos<=P.size()(P的字符总个数)
*/
int KMP_index(const string &P,const string &T,int pos)
{
    int *next=new int[T.size()+2];//动态分配next数组
    get_next(T,next);
    int i=0,j=pos;
    while(i<T.size()&&j<P.size())
    {
        if(i==-1||P[j]==T[i])
        {
            j++;
            i++;
        }
        else
            i=next[i];
    }
    delete []next;
    if(i>=T.size())
        return j-i;
    return -1;
}
int main()
{
    char *T,*P;
    T=new char[100];
    P=new char[100];
    cin>>P>>T;
    cout<<KMP_index(P,T,0)<<endl;
    return 0;
}

原文：http://www.cnblogs.com/flipped/p/5015722.html

内容总结

以上是互联网集市为您收集整理的模式匹配KMP算法全部内容，希望文章能够帮你解决模式匹配KMP算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1331763.html

来源：【匿名】