拓展KMP及应用

核心代码（求next数组和extend数组）：

const int N=5e4+5;
char s1[N],s2[N];
int nxt[N],extend[N];
void getNext(char s[])//模式串
{
    int ls=strlen(s),i=0;
    nxt[0]=ls;
    while(i<ls&&s[i]==s[i+1])
        i++;
    nxt[1]=i;
    int k=1;//已知的最大匹配的开始位置
    for(int i=2;i<ls;i++)
    {
        int len=k+nxt[k];//已知的最大匹配的结束位置
        nxt[i]=min(nxt[i-k],max(0,len-i));
        while(i+nxt[i]<ls&&s[nxt[i]]==s[i+nxt[i]])//如果已知的最大匹配不能满足要求，继续判断
            nxt[i]++;
        if(i+nxt[i]>k+nxt[k])//更新已知的最大匹配
            k=i;
    }
}
void getExtend(char sa[],char sb[])//主串，模式串
{//与求next数组的步骤一样，不够是两个不同的字符串之间
    getNext(sb);
    int i=0,la=strlen(sa),lb=strlen(sb);
    while(sa[i]==sb[i]&&i<la&&i<lb)
        i++;
    extend[0]=i;
    int k=0;
    for(int i=1;i<la;i++)
    {
        int len=k+extend[k];
        extend[i]=min(nxt[i-k],max(0,len-i));
        while(i+extend[i]<la&&extend[i]<lb&&sb[extend[i]]==sa[i+extend[i]])//多了一个条件
            extend[i]++;
        if(i+extend[i]>k+extend[k])
            k=i;
    }
}

模板题：
Simpsons’ Hidden Talents HDU - 2594
可以用KMP解决：
KMP--------代码：

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+5;
char s1[N],s2[N];
int nxt[N];
void getNext()
{
    int len=strlen(s1);
    int i=0,j=-1;
    nxt[0]=-1;
    while(i<len)//比一般的要多计算一位next数组值
    {
        if(j==-1||s1[i]==s1[j])
            nxt[++i]=++j;
        else
            j=nxt[j];
    }
}
int main()
{
    while(scanf("%s%s",s1,s2)!=EOF)
    {
        getNext();
        int i=0,j=0,len1=strlen(s1),len2=strlen(s2);
        while(i<len2)//因为要求s2的后缀，所有s2必须匹配完全
        {
            if(j==-1||(s1[j]==s2[i]&&j<len1))
                i++,j++;
            else
                j=nxt[j];
        }
        for(int i=0;i<j;i++)
        {
            printf("%c",s1[i]);
            if(i==j-1)
                printf(" ");
        }
        printf("%d\n",j);
    }
    return 0;
}

拓展KMP-----代码：

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+5;
char s1[N],s2[N];
int nxt[N],extend[N];
void getNext(char s[])//模式串
{
    int ls=strlen(s),i=0;
    nxt[0]=ls;
    while(i<ls&&s[i]==s[i+1])
        i++;
    nxt[1]=i;
    int k=1;//已知的最大匹配的开始位置
    for(int i=2;i<ls;i++)
    {
        int len=k+nxt[k];//已知的最大匹配的结束位置
        nxt[i]=min(nxt[i-k],max(0,len-i));
        while(i+nxt[i]<ls&&s[nxt[i]]==s[i+nxt[i]])//如果已知的最大匹配不能满足要求，继续判断
            nxt[i]++;
        if(i+nxt[i]>k+nxt[k])//更新已知的最大匹配
            k=i;
    }
}
void getExtend(char sa[],char sb[])//主串，模式串
{//与求next数组的步骤一样，不够是两个不同的字符串之间
    getNext(sb);
    int i=0,la=strlen(sa),lb=strlen(sb);
    while(sa[i]==sb[i]&&i<la&&i<lb)
        i++;
    extend[0]=i;
    int k=0;
    for(int i=1;i<la;i++)
    {
        int len=k+extend[k];
        extend[i]=min(nxt[i-k],max(0,len-i));
        while(i+extend[i]<la&&extend[i]<lb&&sb[extend[i]]==sa[i+extend[i]])//多了一个条件
            extend[i]++;
        if(i+extend[i]>k+extend[k])
            k=i;
    }
}
int main()
{
    while(scanf("%s%s",s1,s2)!=EOF)
    {
        getExtend(s2,s1);
        int len=strlen(s2);
        int ans=0;
        for(int i=0;i<len;i++)
        {
            if(i+extend[i]==len)
            {
                ans=extend[i];
                break;
            }
        }
        for(int i=0;i<ans;i++)
            printf("%c",s1[i]);
        if(ans>0)
            printf(" ");
        printf("%d\n",ans);
    }
    return 0;
}

Clairewd’s message HDU - 4300
AC代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char s[30],text[N],sp[30];
int nxt[N],extend[N];
void getNext(char ss[])
{
    int ls=strlen(ss),i=0;
    nxt[0]=ls;
    while(i<ls&&ss[i]==ss[i+1])
        i++;
    nxt[1]=i;
    int k=1;
    for(int i=2;i<ls;i++)
    {
        int len=k+nxt[k];
        nxt[i]=min(nxt[i-k],max(0,len-i));
        while(i+nxt[i]<ls&&ss[nxt[i]]==ss[i+nxt[i]])
            nxt[i]++;
        if(i+nxt[i]>k+nxt[k])
            k=i;
    }
}
void getExtend(char sa[],char sb[])
{
    getNext(sb);
    int la=strlen(sa),lb=strlen(sb),i=0;
    while(s[sa[i]-'a']==sb[i]&&i<la&&i<lb)
        i++;
    extend[0]=i;
    int k=0;
    for(int i=1;i<la;i++)
    {
        int len=k+extend[k];
        extend[i]=min(nxt[i-k],max(0,len-i));//把nxt[i]写成了extend[i]，t了几个小时
        while(i+extend[i]<la&&extend[i]<lb&&s[sa[i+extend[i]]-'a']==sb[extend[i]])
            extend[i]++;
        if(i+extend[i]>k+extend[k])
            k=i;
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s);
        scanf("%s",text);
        memset(nxt,0,sizeof(nxt));
        memset(extend,0,sizeof(extend));
        getExtend(text,text);
        int len=strlen(text);
        int p=len;
        for(int i=0;i<26;i++)
            sp[s[i]-'a']=('a'+i);
        for(int i=0;i<len;i++)
        {
            if(i>=extend[i]&&extend[i]==len-i)
            {
                p=i;
                break;
            }
        }
        cout<<text;
        for(int i=len-p;i<p;i++)
            cout<<sp[text[i]-'a'];
        cout<<endl;
    }
    return 0;
}