exKMP算法 （模板+图片加深理解）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了exKMP算法 （模板+图片加深理解），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2762字，纯文字阅读大概需要4分钟。

内容图文

先上代码：

const int maxn=100010;   //字符串长度最大值
int nt[maxn],ex[maxn]; //ex数组即为extend数组
///预处理计算next数组
void GETNEXT(char *str)
{
    int i=0,j,po,len=strlen(str);
    nt[0]=len;///用自己作为后缀与自己匹配
    while(str[i]==str[i+1]&&i+1<len) i++;///暴力求next[1]
    nt[1]=i;

    po=1;///从此点出发next数组延伸位置最远
    for(i=2;i<len;i++)
    {
        if(nt[i-po]< nt[po]+po-i )///第一种情况，可以直接得到next[i]的值
        nt[i]=nt[i-po];
        else///第二种情况，要继续匹配才能得到next[i]的值
        {
            j=nt[po]+po-i;
            if(j<0)j=0; ///小于0表示没有已知相同部分，重新开始匹配
            while(i+j<len&&str[j]==str[j+i])
            j++;
            nt[i]=j;
            po=i;///更新po的位置
        }
    }
}
///计算extend数组
void EXKMP(char *s1,char *s2)
{
    int i=0,j,po,len=strlen(s1),l2=strlen(s2);
    GETNEXT(s2);
    while(s1[i]==s2[i]&&i<l2&&i<len)
    i++;
    ex[0]=i;
    po=0;
    for(i=1;i<len;i++)
    {
        if(nt[i-po]<ex[po]+po-i)
        ex[i]=nt[i-po];
        else
        {
            j=ex[po]+po-i;
            if(j<0)j=0;
            while(i+j<len&&j<l2&&s1[j+i]==s2[j])
            j++;
            ex[i]=j;
            po=i;
        }
    }
}

exKMP用于解决寻找一个串与另一个串的所有后缀的最长相同前缀

①为什么exKMP称为扩展KMP呢？

因为构造数组的思路和KMP是一样一样的。（暗示先理解KMP）

（但是构造出来的数组意义不一样。不要撒敷敷用KMP里面的失配数组来理解构造过程）

我们给用自身构造数组的那个串叫做ss，另一个叫做s

KMP：

失配数组的含义：fail[i] 表示ss 0~i-1这个前缀的最长相同前后缀

构造的时候利用已知利用已知匹配长度（也就是当前失配指针的位置），尝试匹配当前位置和失配指针的位置的字符。

利用失配数组找s中的ss：

与上面构造失配数组的不同就是此时构造过程的参照不是自身s了，而是ss，此时是在求s中当前位置为结尾的这一部分串

的后缀和ss的前缀的最长相同部分。

exKMP：

next数组的含义：next[i]表示s当前位置开始的这部分串和开头开始的串的最长相同前缀

也是利用一直相同部分来尽可能减少匹配次数

利用next构造extend数组：

也是以ss为参照来匹配s的过程，表示s当前位置开始的串和ss的最长相同前缀。（不要在这里尝试理解，这里粗略讲一下）

②exKMP模板的详细（也许）的讲解

用于求串A的所有后缀与串B的最长相同前缀

exKMP有两个数组：

next[i]:     B串   i  ~  strlen（B）-1      部分与 B自身的最长相同前缀

extend[i]:      A串   i  ~  strlen（A）-1        部分与B的最长相同前缀，也就是我们要求的东西。

第一部分：next数组的构造

PO 表示当下next数组延伸位置最远的那个下标，要问我这个保存这个有什么用？

比方说现在PO = 3，next[PO] = 4,即【0,3】==【3,6】

你要求i = 5时的next，那么，你是不是已经知道【5,6】 ==【2,3】

你又问我：你给我知道等于【2,3】有什么用，我要知道从头开始已经有几位匹配了！！！

我上去就给你一巴掌：你自己不会查一下next[2]，看看有几位匹配？！

如果你查到了next[2]=1：那么恭喜你next[5] 就等于 1了，因为答案已经有了，只匹配一位。

但是如果你查到了2或者更大呢：那么恭喜你，前两位已经匹配了，接下来还需要你手动继续匹配

用于理解的图：

然后你发现你并不理解为什么j会小于0，所以你又看了这张图

  这么一来next数组构造基本没有问题啦。

第二部分：extend数组的构造

其实没什么好讲了，无非就是刚才用来参照匹配的是自身，现在是B串。

工地事务繁忙，告辞！

 

 

 

 

内容总结

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

内容备注

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

内容手机端

---