P9606 [CERC2019] ABB 题解

· · 题解

传送门

题面简述：

给定一个字符串，问至少要在字符串末加多少个字符，使原串变成回文串。

思路：

为什么找后缀的回文：

显然，加的字符数量不会超过原串的长度（任何串倒序复制一遍以合法的）。

由于最后的字符串是回文的，所以回文中心要么在原串中，要么在原串和添加串之间。

如图，因为回文中心在原串中，所以它在原串中必定会有回文串（用绿色表示），这就是后缀的回文。

为什么找最长的回文：

黄色和绿色部分表示回文串

如图，找的回文越长，修改后的串越短。而且我们还知道了，问题的答案就是黑色串的长度=原串长度-最长后缀回文长度。于是问题就变成了求最长后缀回文长度。

怎么找最长回文：

考虑到 manacher 记录的是到当前最长的回文串长度，用 f(i) 表示，并没有保证是后缀。

最妙的来了

我们把字符串倒序（相当于从后往前做 manacher），这时，f(i)=i+1 是目前最长回文是后缀的的充要条件（i 从 0 开始）。这是因为如果 f(i)=i+1 则说明目前最长回文是从 0 开始到 i 的，由于是倒序的，所以它是后缀的。

献上代码：

#include<iostream>
using namespace std;
int n,len,maxx;
int f[4000005];
string ss;
char s[8000005];
int main()
{
    cin>>len>>ss;
    n=(len<<1)+1;
    for(int i=0,j=len-1;i<n;i++) s[i]=i&1?ss[j--]:'#';
    for(int i=0,c=0,r=0;i<n;i++)
    {
        f[i]=r>i?min(f[(c<<1)-i],r-i):1;
        while(i-f[i]>=0&&i+f[i]<n&&s[i-f[i]]==s[i+f[i]]) f[i]++;
        if(i+f[i]>r) r=i+f[i],c=i;
        if(f[i]==i+1) maxx=f[i]-1;
    }
    cout<<len-maxx;
}

完结撒花~