字符串专题

• K m p Kmp Kmp 算法
• M a n a c h e r Manacher Manacher 算法

K m p Kmp Kmp 算法

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Maxn=1e6+2e2;
//Kmp[i] is mean the longest same preifx and suffix's len.
int Kmp[Maxn],lena,lenb,j;
char Sa[Maxn],Sb[Maxn];
int main()
{
    scanf("%s%s",Sa+1,Sb+1);
    lena=strlen(Sa+1);
    lenb=strlen(Sb+1);
    //Kmp[1]=0;
    for(int i=2;i<=lenb;i++)
    {
        while(j&&Sb[i]!=Sb[j+1])j=Kmp[j];
        //[1-j] is prefix [i-j i-1] is suffix.
        //if(Sb[i]!=Sb[j+1]) new prefix unmatch with new suffix.
        //j=kmp[j].
        if(Sb[i]==Sb[j+1])j++;
        Kmp[i]=j;
    }
    j=0;
    for(int i=1;i<=lena;i++)
    {
        while(j&&Sb[j+1]!=Sa[i])j=Kmp[j];
        if(Sb[j+1]==Sa[i])j++;
        if(j==lenb){printf("%d\n",i-lenb+1);j=Kmp[j];}
    }
    for(int i=1;i<=lenb;i++)
        printf("%d ",Kmp[i]);
    return 0;
}

M a n a c h e r Manacher Manacher 算法

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Maxn=3e7;
char St[Maxn],Tmp[Maxn];
int cnt,mid,len,ans,tmp,P[Maxn];
//P[i] is mean if i is mid,the max len of A-A string
inline void Build()
{
    scanf("%s",St+1);
    len=strlen(St+1);
    Tmp[++cnt]='~';
    Tmp[++cnt]='#';
    for(int i=1;i<=len;i++)
    {
        Tmp[++cnt]=St[i];
        Tmp[++cnt]='#';
    }
    Tmp[++cnt]='&';
}
//Make Tmp only have odd A-A string
inline void Work()
{
    for(int i=2;i<=cnt-1;i++)
    {
        if(i<=tmp)P[i]=min(P[mid-(i-mid)],tmp-i+1);
        //P[mid-(i-mid)] have been calced.
        //But if i+P[i]>tmp,P[i]!=P[mid-(i-mid)].
        //P[i] should be tmp-i+1.
        else P[i]=1;
        while(Tmp[i-P[i]]==Tmp[i+P[i]])++P[i];//Update P[i]
        if(i+P[i]>tmp)tmp=i+P[i]-1,mid=i;
        //some A-A string is break,so we update mid.
        ans=max(ans,P[i]);
    }
    printf("%d\n",ans-1);
}
int main()
{
    Build();
    Work();
    return 0;
}