摘自 拓展kmp算法总结

1、扩展KMP是什么？解决何种问题？与KMP算法的异同？

• 拓展kmp是对KMP算法的扩展，它解决如下问题：

  定义母串S，和字串T，设S的长度为n，T的长度为m，求T与S的每一个后缀的最长公共前缀，也就是说，设extend数组,extend[i]表示T与S[i,n-1]的最长公共前缀，要求出所有extend[i](0<=i<n)。

• 注意到，如果有一个位置extend[i]=m,则表示T在S中出现，而且是在位置i出现，这就是标准的KMP问题，所以说拓展kmp是对KMP算法的扩展，所以一般将它称为扩展KMP算法。

• 图例：
  -S=”aaaabaa”，T=”aaaaa”,首先，计算extend[0]时，需要进行5次匹配，直到发生失配。从而得知extend[0]=4。
  

  • 下面计算extend[1]，在计算extend[1]时，是否还需要像计算extend[0]时从头开始匹配呢？答案是否定的，因为通过计算extend[0]=4，从而可以得出S[0,3]=T[0,3]，进一步可以得到 S[1,3]=T[1,3],计算extend[1]时，事实上是从S[1]开始匹配。

2、拓展kmp算法一般步骤

• **1、**首先我们从左到右依次计算extend数组，在某一时刻，设extend[0...k]已经计算完毕，并且之前匹配过程中所达到的最远位置为P，所谓最远位置，严格来说就是i+extend[i]-1的最大值（0<=i<=k）,并且设取这个最大值的位置为po，如在上一个例子中,计算extend[1]时，P=3，po=0。

• **2、**现在要计算extend[k+1],【注意啦！这里我们推的是k+1的公式，而在代码中是写的k的公式，会差一个1，不要搞错咯！】根据extend数组的定义，可以推断出S[po,P]=T[0,P-po],从而得到 S[k+1,P]=T[k-po+1,P-po],令len=next[k-po+1]，(这里len也就是可以从头开始匹配上的字符长度)，分两种情况讨论：

  • 2.1 第一种情况：k+len < P

    • 2.1.1
      也就是说从T字符串的k - po + 1位置推断出的从T的0开头可以匹配的长度len并没有超过现有P的大小，而po - p之间的字符是可以被匹配的这一事实我们已经检验过，所以可以确保从k+1 ~ k + len的字符，确实可以从T头开始匹配len的长度

  • **2.1.2 **

  • 2.1.3
    上图中，S[k+1,k+len]=T[0,len-1]，然后S[k+len+1]一定不等于T[len]，因为如果它们相等，则有S[k+1,k+len+1]=T[k+po+1,k+po+len+1]=T[0,len],那么next[k+po+1]=len+1，这和next数组的定义不符(next[i]表示T[i,m-1]和T的最长公共前缀长度)，所以在这种情况下，不用进行任何匹配，就知道extend[k+1]=len。

  • **2.2 ** 第二种情况：k+len>=P

    • 2.2.1
      也就是说从T字符串的k - po + 1位置推断出的从T的0开头可以匹配的长度len已经超过了现有P的大小，而po - p之间的字符是可以被匹配的这一事实我们已经检验过，但超过p的部分我们并没有匹配过，所以不能确保从k +1~ k + len的字符是否可以从T头开始匹配len的长度，只能说至少可以确定k+1 ~ p是匹配的，而p + 1 ~ k + len的部分还需要进一步比对 。
    • **2.2.2 **
    • 2.2.3
      上图中，S[p+1]之后的字符都是未知的，也就是还未进行过匹配的字符串，所以在这种情况下，就要从S[P+1]和T[P-k+1]开始一一匹配，直到发生失配为止，当匹配完成后，如果得到的extend[k+1]+(k+1)大于P则要更新未知P和po。(得到的extend[k+1]+(k+1)至少都是p,要么就比p还大，所以在更新完extend之后，直接让p= extend即可）。

• **3、**至此，拓展kmp算法的过程已经描述完成，事实上，计算next数组的过程和计算extend[i]的过程完全一样，将它看成是以T为母串，T为字串的特殊的拓展kmp算法匹配就可以了，计算过程中的next数组全是已经计算过的，所以按照上述介绍的算法计算next数组即可。

3、时间复杂度分析

通过上面的算法介绍可以知道，对于第一种情况，无需做任何匹配即可计算出extend[i]，对于第二种情况，都是从未被匹配的位置开始匹配，匹配过的位置不再匹配，也就是说对于母串的每一个位置，都只匹配了一次，所以算法总体时间复杂度是O(n)的，同时为了计算辅助数组next[i]需要先对字串T进行一次拓展kmp算法处理，所以拓展kmp算法的总体复杂度为O(n+m)的。其中n为母串的长度，m为子串的长度。

4、核心代码模板

const int maxn = 100010; //字符串长度最大值
int next[maxn], ex[maxn]; //ex数组即为extend数组
//预处理计算next数组
void GETNEXT(char *str)
{
    int i = 0, j, po, len = strlen(str);
    next[0] = len; //初始化next[0]，因为从0开头就可以匹配整个T，故为len   /*与EXKMP代码不同处：无这句话*/
    while(str[i] == str[i + 1] && i + 1 < len) //计算next[1]  /*与EXKMP代码不同处：比较s1和s2*/
        i++;
    next[1] = i;/*与EXKMP代码不同处：ex[0]=i*/
    po = 1; //初始化po的位置  /*与EXKMP代码不同处：po = 0*/
    for(i = 2; i < len; i++)/*与EXKMP代码不同处：i从1开始*/
    {
        if(next[i - po] + i < next[po] + po) //第一种情况，可以直接得到next[i]的值  /*与EXKMP代码不同处：next[i-po]+i<ex[po]+po*/
            next[i] = next[i - po];/*与EXKMP代码不同处：ex[i]=next[i-po];*/
        else//第二种情况，要继续匹配才能得到next[i]的值
        {
            j = next[po] + po - i;/*与EXKMP代码不同处：j=ex[po]+po-i;*/
            if(j < 0)j = 0; //如果i>po+next[po],则要从头开始匹配
            while(i + j < len && str[j] == str[j + i]) //计算next[i]  /*与EXKMP代码不同处：i+j<len&&j<l2&&s1[j+i]==s2[j]*/
                j++;
            next[i] = j;/*与EXKMP代码不同处：ex[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);//计算子串的next数组
    while(s1[i] == s2[i] && i < l2 && i < len) //计算ex[0]
        i++;
    ex[0] = i;
    po = 0; //初始化po的位置
    for(i = 1; i < len; i++)
    {
        if(next[i - po] + i < ex[po] + po) //第一种情况，直接可以得到ex[i]的值
            ex[i] = next[i - po];
        else//第二种情况，要继续匹配才能得到ex[i]的值
        {
            j = ex[po] + po - i;
            if(j < 0)j = 0; //如果i>ex[po]+po则要从头开始匹配
            while(i + j < len && j < l2 && s1[j + i] == s2[j]) //计算ex[i]
                j++;
            ex[i] = j;
            po = i; //更新po的位置
        }
    }
}

先贴一波kmp和manacher的博客,对于理解这个很有用:

https://blog.csdn.net/qq_49593247/article/details/120077670?spm=1001.2014.3001.5501

拓展kmp函数(z函数)在竞赛中比较冷门,但是学习了z函数会提升对于manacher和kmp这一类的字符串处理算法的理解.它本身其实也是按照的kmp的思想.

扩展KMP求的是对于文本串S1的每一个后缀子串与模式串S2的最长公共前缀,类似于manacher算法,它也会存一个右端点在已经匹配过的点的最右端的点.它还存在一个next数组和extend数组,next数组含义类似于kmp的next数组,所存的数据是从模式串第i位开始和它的第一位匹配匹配,所匹配的最长前缀的长度.而extend数组则是存的文本串和模式串相匹配的该结果.

例如:有文本串aaaabba和模式串aaaaa.

 为什么我们要预先处理一个next数组呢,类似于kmp算法,当在匹配过程中,模式串的前缀和文本串后缀所匹配的长度的值其实就等于模式串自己和自己匹配,因为匹配了此时两者是相等的,那么就可以在文本串与模式串匹配时直接用next来获取模式串长度为i时最长的公共前缀长度.

然后就是匹配的思想了.

我们会存一个两个字符串相等是能匹配的最长长度的起点p,并且用一个now值去记录该字符串的长度.所以一开始我们没有进行匹配,所以我们就要去求此时的起点和匹配的长度:

    int now=0;//此时没有进行匹配,长度就是0
    while(str1[now]==str[now]&&now<len1&&now<len)
        now++;//从0开始匹配,字符相匹配那么长度就增加    
    extend[0]=now;//文本串从0开始的后缀与模式串相匹配的长度
    int p=0;//记录起点

储存之后,我们从1开始匹配,匹配时就会出现两种情况:

1.i+nex[i-p]<p+extend[p]

第一种情况从当前位置i开始(此时1到n-1的nex值和extend值已经算出来了).p是之前匹配的最右串的起点,p没有更新,所以i-p就是指此时文本串和模式串已经匹配的长度,因为此时文本串的p和模式串的头是对在一起的.所以i+nex[i-p]就是指模式串从i加上此时从i开始的模式串的后缀和模式串前缀匹配的最长前缀的长度(此时p到nex[p]以及全部是相等的了,可以看做是模式串的一部分)的位置.此时extend[i]的值就是此长度(i-p)的next值,也就是截取的模式串i开始的后缀和模式串前缀相等的这段的最长公共前缀的长度.

if(i+nex[i-p]<p+extend[p])extend[i]=nex[i-p];

2.i+nex[i-p]>=p+extend[p]

当超过存的最长匹配串的右端时,因为右端没有进行匹配,说明此时i开始往后的这个匹配串会成为新的最右端匹配串,所以我们就暴力往后匹配,此处有一个类似于kmp的往后移动模式串的过程.将模式串的头对准i,然后因为之前的预处理,到p+extend[p]为止,两个串已经匹配好了,那么再往后面暴力匹配即可:

        else
        {
            now=p+extend[p]-i;
            now=max(now,0);//防止出现负数
            while(str[now+i]==str1[now]&&now+i<len&&now<len1)
            {
                now++;
            }//包里匹配
            extend[i]=now;
            p=i;//更新
        }

 这就是拓展kmp的大致流程,接下来就整一个洛谷的模板题,把代码贴上去:

https://www.luogu.com.cn/problem/P5410

#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
char str[20000007],str1[20000007];
//str为文本串,str1是模式串
ll nex[20000007],extend[20000007],len,len1;
void getnex()//对模式串进行匹配
{
    nex[0]=len1;
    int now=0;
    while(str1[now]==str1[now+1]&&now+1<len1)now++;
    nex[1]=now;
    int p=1;
    for(int i=2;i<len1;i++)
    {
        if(i+nex[i-p]<p+nex[p])nex[i]=nex[i-p];
        else
        {
            now=p+nex[p]-i;
            now=max(now,0);
            while(str1[now+i]==str1[now]&&now+i<len1)
            {
                now++;
            }
            nex[i]=now;
            p=i;
        }
    }
    return ;
}
void getextend()//模式串与文本串匹配
{
    getnex();
    int now=0;
    while(str1[now]==str[now]&&now<len1&&now<len)now++;
    extend[0]=now;
    int p=0;
    for(int i=1;i<len;i++)
    {
        if(i+nex[i-p]<p+extend[p])extend[i]=nex[i-p];
        else
        {
            now=p+extend[p]-i;
            now=max(now,0);
            while(str[now+i]==str1[now]&&now+i<len&&now<len1)
            {
                now++;
            }
            extend[i]=now;
            p=i;
        }
    }
    return ;
}
int main()
{
    scanf("%s%s",str,str1);
    len=strlen(str);
    len1=strlen(str1);
    ll z=0,p=0;
    getextend();
    for(int i=0;i<len1;i++)
    {
        z^=1ll*(i+1)*(nex[i]+1);
    }
    for(int i=0;i<len;i++)
    {
        p^=1ll*(i+1)*(extend[i]+1);
    }
    printf("%lld\n%lld\n",z,p);
    return 0;
}

其实拓展kmp思想也是从kmp而来,所以学好kmp很重要!

https://blog.csdn.net/dyx404514/article/details/41831947

拓展kmp是对KMP算法的扩展，它解决如下问题：

定义母串S，和字串T，设S的长度为n，T的长度为m，求T与S的每一个后缀的最长公共前缀，也就是说，设extend数组,extend[i]表示T与S[i,n-1]的最长公共前缀，要求出所有extend[i](0<=i<n)。

注意到，如果有一个位置extend[i]=m,则表示T在S中出现，而且是在位置i出现，这就是标准的KMP问题，所以说拓展kmp是对KMP算法的扩展，所以一般将它称为扩展KMP算法。

下面举一个例子，S=”aaaabaa”,T=”aaaaa”,首先，计算extend[0]时，需要进行5次匹配，直到发生失配。

从而得知extend[0]=4，下面计算extend[1],在计算extend[1]时，是否还需要像计算extend[0]时从头开始匹配呢？答案是否定的，因为通过计算extend[0]=4，从而可以得出S[0,3]=T[0,3]，进一步可以得到 S[1,3]=T[1,3],计算extend[1]时，事实上是从S[1]开始匹配，设辅助数组next[i]表示T[i,m-1]和T的最长公共前缀长度。在这个例子中，next[1]=4,即T[0,3]=T[1,4],进一步得到T[1,3]=T[0,2],所以S[1,3]=T[0,2],所以在计算extend[1]时，通过extend[0]的计算，已经知道S[1,3]=T[0,2],所以前面3个字符已经不需要匹配，直接匹配S[4]和T[3]即可，这时一次就发生失配，所以extend[1]=3。这个例子很有代表性，有兴趣的读者可以继续计算完剩下的extend数组。

1. 拓展kmp算法一般步骤

通过上面的例子，事实上已经体现了拓展kmp算法的思想，下面来描述拓展kmp算法的一般步骤。

首先我们从左到右依次计算extend数组，在某一时刻，设extend[0...k]已经计算完毕，并且之前匹配过程中所达到的最远位置为P，所谓最远位置，严格来说就是i+extend[i]-1的最大值（0<=i<=k）,并且设取这个最大值的位置为po，如在上一个例子中,计算extend[1]时，P=3，po=0。

现在要计算extend[k+1],根据extend数组的定义，可以推断出S[po,P]=T[0,P-po],从而得到 S[k+1,P]=T[k-po+1,P-po],令len=next[k-po+1]，(回忆下next数组的定义),分两种情况讨论：

第一种情况：k+len<P

如下图所示：

上图中，S[k+1,k+len]=T[0,len-1]，然后S[k+len+1]一定不等于T[len]，因为如果它们相等，则有S[k+1,k+len+1]=T[k+po+1,k+po+len+1]=T[0,len],那么next[k+po+1]=len+1，这和next数组的定义不符(next[i]表示T[i,m-1]和T的最长公共前缀长度)，所以在这种情况下，不用进行任何匹配，就知道extend[k+1]=len。

第二种情况： k+len>=P

如下图：

上图中，S[p+1]之后的字符都是未知的，也就是还未进行过匹配的字符串，所以在这种情况下，就要从S[P+1]和T[P-k+1]开始一一匹配，直到发生失配为止，当匹配完成后，如果得到的extend[k+1]+(k+1)大于P则要更新未知P和po。

至此，拓展kmp算法的过程已经描述完成，细心地读者可能会发现，next数组是如何计算还没有进行说明，事实上，计算next数组的过程和计算extend[i]的过程完全一样，将它看成是以T为母串，T为字串的特殊的拓展kmp算法匹配就可以了，计算过程中的next数组全是已经计算过的，所以按照上述介绍的算法计算next数组即可，这里不再赘述。

2. 时间复杂度分析

下面来分析一下算法的时间复杂度，通过上面的算法介绍可以知道，对于第一种情况，无需做任何匹配即可计算出extend[i]，对于第二种情况，都是从未被匹配的位置开始匹配，匹配过的位置不再匹配，也就是说对于母串的每一个位置，都只匹配了一次，所以算法总体时间复杂度是O(n)的，同时为了计算辅助数组next[i]需要先对字串T进行一次拓展kmp算法处理，所以拓展kmp算法的总体复杂度为O(n+m)的。其中n为母串的长度，m为子串的长度。

下面是拓展kmp算法的关键部分代码实现。

const int maxn=100010;   //字符串长度最大值
int next[maxn],ex[maxn]; //ex数组即为extend数组
//预处理计算next数组
void GETNEXT(char *str)
{
    int i=0,j,po,len=strlen(str);
    next[0]=len;//初始化next[0]
    while(str[i]==str[i+1]&&i+1<len)//计算next[1]
    i++;
    next[1]=i;
    po=1;//初始化po的位置
    for(i=2;i<len;i++)
    {
        if(next[i-po]+i<next[po]+po)//第一种情况，可以直接得到next[i]的值
        next[i]=next[i-po];
        else//第二种情况，要继续匹配才能得到next[i]的值
        {
            j=next[po]+po-i;
            if(j<0)j=0;//如果i>po+next[po],则要从头开始匹配
            while(i+j<len&&str[j]==str[j+i])//计算next[i]
            j++;
            next[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);//计算子串的next数组
    while(s1[i]==s2[i]&&i<l2&&i<len)//计算ex[0]
    i++;
    ex[0]=i;
    po=0;//初始化po的位置
    for(i=1;i<len;i++)
    {
        if(next[i-po]+i<ex[po]+po)//第一种情况，直接可以得到ex[i]的值
        ex[i]=next[i-po];
        else//第二种情况，要继续匹配才能得到ex[i]的值
        {
            j=ex[po]+po-i;
            if(j<0)j=0;//如果i>ex[po]+po则要从头开始匹配
            while(i+j<len&&j<l2&&s1[j+i]==s2[j])//计算ex[i]
            j++;
            ex[i]=j;
            po=i;//更新po的位置
        }
    }
}