KMP，EXKMP 扩展KMP

大家好，欢迎来到IT知识分享网。

EXKMP是KMP算法的一个扩展和加难，可以解决一些KMP无法解决的问题
先回顾一下KMP

KMP

KMP的关键是next数组
next[i]表示的是s[1~next[i]]=s[i-next[i]+1~i]
在进行字符串匹配时如将s和t匹配时
如果t[i+1]和s[j+1]不对时，可以将t[i+1]和s[next[j]+1]进行匹配，因为next数组满足上面的性质，可以保证s[1~next[j]]和t对应的位置完全相同，这样对于每个t[i]就只用匹配一次，时间是线性的
next数组也能线性的求出来
假设next[1~j]已经求出，接下来求next[j+1]
同样利用next[]数组的性质，可以发现如果s[j+1]=s[next[j]+1]，那么next[j+1]=next[j]+1
如果s[j+1]不等于s[next[j]+1]，那么继续将s[j+1]和s[next[next[j]]+1]进行匹配
请自行画图，利用next[]的性质很容易理解

代码如下

void kmp()
{
    int j=0;
    fo(i,2,n)
    {
        while(j>0&&s[j+1]!=s[i]) j=next[j];
        if(s[j+1]==s[i]) j++;
        next[i]=j;
    }
}

还有一个和KMP思想很像的算法，KMP是单字符串匹配，那个是多字符串匹配，那就是AC自动机，点击进入

EXKMP

正题来了
EXKMP也有一个关键的数组extend[]
对于两个字符串s,t
extend[i]表示s以i开头的后缀与t的前缀相同的长度
即s[i~i+extend[i]-1]=t[1~extend[i]]
怎么求呢，设在枚举到i之前最大的i+extend[i]为p，对应的i为a
也就是s[a~p]=t[1~p-a+1]
同时再设一个next数组表示t[1~next[i]]=t[i~i+next[i]-1]
以下请画图，否则很难理解
那么在求extend[i]的时候，只需要从next[i-a+1]进行匹配了
因为:
s[a~p]=t[1~p-a+1]
s[i~p]=t[i-a+1~p-a+1]
t[i-a+1~i-a+1+next[i-a+1]]
s[i~p]=t[1~next[i-a+1]]
显然，这样做的话，p会不断增加，而如果next[i-a+1]比p小的话就不需要匹配，最终每个字符也只会算一次，所以时间是线性的
next数组怎么求呢？你会发现，next的定义实际上和extend的定义差不多，所以求法也差不多
模板题beyond

代码如下

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 101000
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
char s[N],t[N];
int next[N],extend[N],n,m,nm;
void getextend()
{
    next[1]=n;
    int a=0,p=0;
    fo(i,2,n)
    {
        int j=next[i-a+1];
        if(i+j>p) for(j=max(0,p-i);i+j<=n && t[i+j]==t[j+1];j++);
        next[i]=j;
        if(i+j-1>p) a=i,p=i+j-1;
    }
    a=p=0;
    fo(i,1,n)
    {
        int j=next[i-a+1];
        if(i+j>p) for(j=max(0,p-i+1);i+j<=n && s[i+j]==t[j+1];j++);
        extend[i]=j;
        if(i+j-1>p) a=i,p=i+j-1;
    }
}
int main()
{
    freopen("exkmp.in","r",stdin);
    scanf("%s\n",s+1);n=strlen(s+1);
    scanf("%s\n",t+1);
    getextend();
    fo(i,1,n) printf("%d ",extend[i]);
}