ABB 马拉车求回文后缀

题意

　　给你一个长度为n的字符串，要求往字符串右边添加尽可能少的字符串，使整个字符串为回文串。

思路

　　尽可能少就是添加 n-该数组的最大回文后缀 个就行。

　　首先跑一遍马拉车，求得num数组，num[i]为填充字符后的字符串第i位的回文半径，所以num[i]+i==len-1时，此时的回文子串是紧贴右边的，于是维护一下num[i]-1，代表原来字符串的回文长度，输出n-maxx即可AC。

AC代码

#include<iostream>
#include<string.h> 
using namespace std;
const int maxn=4e5+5;
char s[maxn<<1],str[maxn<<1];
int len,num[maxn*2];
int n;
void getstr()
{//重定义字符串，s为原字符串，str为新串,len为s串长度 
    int k=0;
    str[k++]='@';
    for(int i=0;i<len;i++){
        str[k++]='#';
        str[k++]=s[i];
    } 
    str[k++]='#';
    str[k++]='0';
    len=k;
}
int manacher(){
    int mx=0,id;
    int maxx=0;
    for(int i=0;i<len;i++){
        if(i<mx) num[i]=min(mx-i,num[2*id-i]);//i在mx左边，取在边界以内且较小的那段 
        else num[i]=1;//i在mx右边，所以直接等于1 
        while(str[i+num[i]]==str[i-num[i]]) num[i]++;//向右一个个匹配 
        if(i+num[i]>mx){
            mx=i+num[i];
            id=i;
            maxx=max(maxx,num[i]-1);
        }
    }
    return maxx;
} 
int main()
{
    cin>>n;
    cin>>s;
    len=n;
    getstr();
    manacher();
    int maxx=-1;
    for(int i=0;i<len;i++){
        //cout<<i<<" "<<num[i]<<endl;
        if(i+num[i]==len-1){
            maxx=max(maxx,num[i]-1);
        }
    }
    cout<<n-maxx;
    return 0;
}