P4555题解

和其他题解一样，求以一个字符为左或右端点，最长的回文子串长度。

我的思路是直接在 Manacher 的过程中求出

l

和

r

数组（其中

l_i

表示以

i

为右端点，向左最长的回文串的长度，

r_i

表示以

i

为左端点，向右最长的回文串的长度。

在正常的 Manacher 中，我们可能将当前考虑的字符的回文串长度暴力扩张，并且向右扩张扫到的字符一定是第一次被扫到的。这也就说明现在在扩张的串左边开始第一个能包含扫到字符的回文串。贪心地想，如果后面再来一个串可以包含扫到的字符，则回文串的中心点一定在现在考虑的字符的右边，因此回文串长度一定不如当前。

因此就可以直接将扫到的字符的

l

设为当前回文串的长度。要求出

r

，从右往左跑一边 Manacher 即可。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;

char a[MAXN], s[MAXN<<1];
int n;
int d[MAXN<<1], d2[MAXN<<1]; //用于记录回文串长度
int l[MAXN<<1], r[MAXN<<1];
int ans;

inline void init() //插入
{
    s[0] = '#';
    s[1] = '$';
    int cnt = 1;
    for(int i = 1;i <= n;i++)
    {
        s[++cnt] = a[i];
        s[++cnt] = '$';
    }
    n = cnt;
    s[n+1] = '~';
}

int main()
{
    scanf("%s", a+1);
    n = strlen(a+1);
    init();
    for(int i = 1, x = 0;i <= n;i++) //从左往右扫的 Manacher
    {
        if(i <= x + d[x]) d[i] = min(d[2*x-i], x+d[x]-i);
        for(;s[i-d[i]-1] == s[i+d[i]+1];) d[i]++, l[i+d[i]] = d[i];
        if(x+d[x] < i+d[i]) x = i;
    }
    for(int i = n, x = n+1;i >= 1;i--) //从右往左扫的 Manacher
    {
        if(i >= x - d2[x]) d2[i] = min(d2[2*x-i], i-x+d2[x]);
        for(;s[i-d2[i]-1] == s[i+d2[i]+1];) d2[i]++, r[i-d2[i]] = d2[i]; //在这里直接给
        if(x-d2[x] > i-d2[i]) x = i;
    }
    for(int i = 3;i < n;i += 2)
    {
        ans = max(ans, l[i] + r[i]);
    }
    printf("%d", ans);
    return 0;
}

文章操作

代码

相关推荐

评论

P4555题解