bzoj2565 最长双回文串

2565: 最长双回文串

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2730 Solved: 1377
[Submit][Status][Discuss]

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。
输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。

Input

一行由小写英文字母组成的字符串S。

Output

一行一个整数，表示最长双回文子串的长度。

Sample Input

baacaabbacabb

Sample Output

HINT

样例说明

从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。

对于100%的数据，2≤|S|≤10^5

2015.4.25新加数据一组

Source

2012国家集训队Round 1 day2

分析：思路比较容易想到：记录第i个字符往左能延伸的回文串的最大长度和第i+1个字符能往右延伸的回文串的最大长度.最后枚举i两个答案加一下取个最大值就是最终答案了.要用到manacher算法，只不过因为要插入'#'和坐标的变换，非常容易写挂，这道题也有一些小优化.

首先统计答案的i一定要对应的是字符，而不是'#',因为更新的时候是更新的能延伸到的字符,利用每个点的回文半径能到达的点的坐标差来更新的,如果统计'#'的答案可能会多. 至于如何求延伸的回文串的最大长度，可以O(n)实现，即每次记录往右已经延伸到哪了(mx),因为i是递增枚举的，所以回文半径覆盖到的点在这个时候更新一定是最优的，每次更新在mx以外，回文半径以内的点.往右延伸的话倒着做一遍就好了.

manacher算法要特别注意+1,-1的问题，以及是否统计插入字符的答案.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

char s[300010], ss[300010];
int ans, len, r[300010], f1[300010], f2[300010], n;

void init()
{
    int p = 1, mx = 1;
    for (int i = 1; i <= n; i++)
    {
        int x = 0;
        if (i < mx)
            x = min(r[p * 2 - i], mx - i);
        else
            x = 1;
        while (ss[i + x] == ss[i - x])
            x++;
        r[i] = x;
        if (i + x > mx)
        {
            mx = i + x;
            p = i;
        }
    }
}

int main()
{
    scanf("%s", s + 1);
    len = strlen(s + 1);
    s[0] = '(';
    for (int i = 1; i <= len; i++)
        ss[++n] = '#', ss[++n] = s[i];
    ss[++n] = '#';
    ss[n + 1] = ')';
    init();
    int mx = 1;
    for (int i = 1; i <= n; i++)
        if (i + r[i] > mx)
        {
        for (int j = mx + 1; j <= i + r[i]; j++)
            f1[j] = j - i + 1;
        mx = i + r[i] - 1;
        }
    mx = n;
    for (int i = n; i >= 1; i--)
        if (i - r[i] < mx)
        {
        for (int j = mx - 1; j >= i - r[i]; j--)
            f2[j] = i - j + 1;
        mx = i - r[i] + 1;
        }
    for (int i = 1; i <= n - 3; i++)
        if (ss[i] != '#')
        ans = max(ans, f1[i] + f2[i + 2]);
    printf("%d\n", ans);

    return 0;
}

秒客网