51nod 1395 两个回文 题解

发表于 | 更新于 | 阅读次数：
本文字数： 839 字 | 阅读时长 ≈ 4 分钟

题意简述

多组数据。每次给定一个字符串$S$，$|S|<=1e5$，请从$S$中选择两个不相交的回文子串使得这两个子串的长度和最大。

思路框架

对于每个位置，求出前缀和后缀中最长回文子串。然后枚举断点，更新答案。

具体思路

首先考虑如何求出前缀和后缀中的最长回文子串。

然后我们珂以先求最长回文后缀（简称$LPS$，即$Longest Palindrome Suffix$）和最长回文前缀（简称$LPP$，即$Longest Palindrome Prefix$）。$LPS[i]$表示以$i$为结尾的前缀的最长回文后缀，$LPP[i]$表示以$i$开头的后缀的最长回文前缀。然后，只要求$LPS$的前缀最大值，$LPP$的后缀最大值，就是前缀/后缀中的最长回文子串了。

$LPP$和$LPS$都很好求，就是回文自动机的板子。正着跑一遍求出$LPS$，反着跑一遍求出$LPP$。

原地修改前缀/后缀最大值。然后用$LPS[i]+LPP[i+1]$更新答案即珂。这个式子的含义是：一个回文子串在$i$左边，一个回文子串在$i$右边，也就是上文说的“枚举断点”。

提示

代码很长，从Soviet函数开始看代码哦，这样方便理清结构。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)

    char s[N];int n;
    void Input()
    {
        scanf("%s",s+1);n=strlen(s+1);
    }

    class Palindrome_Tree
    {
    public:
        char s[N];
        struct node
        {
            int len,fail;
            int ch[26];
        }t[N];
        node& operator[](int id){return *(t+id);}
        int last;
        int cnt=1;
        void Init(char ss[N])
        {
            FK(t);
            strcpy(s+1,ss+1);
            t[0].len=0;t[0].fail=1;
            t[1].len=-1;t[1].fail=0;
            cnt=1;
            last=0;
        }

        int Getfail(int fa,int pos)
        {
            int cur=t[fa].fail;
            for(;s[pos]!=s[pos-t[cur].len-1];cur=t[cur].fail); 

            int id=s[pos]-'a';return t[cur].ch[id];
        }
        void Insert(int pos)
        {
            int cur=last;
            while(s[pos-t[cur].len-1]!=s[pos])
            {
                cur=t[cur].fail;
            }

            int id=s[pos]-'a';
            if (t[cur].ch[id]==0)
            {
                ++cnt;
                t[cnt].len=t[cur].len+2;
                t[cnt].fail=Getfail(cur,pos);
                t[cur].ch[id]=cnt;
            }
            last=t[cur].ch[id];
        }
    }T; //普通的回文自动机

    int LPS[N],LPP[N];
    void Soviet()
    {
        FK(LPS),FK(LPP);
        T.Init(s);F(i,1,n) T.Insert(i),LPS[i]=T[T.last].len;//正着跑一遍求出LPS，以i结尾的前缀的最长回文后缀

        reverse(s+1,s+n+1);
        T.Init(s);F(i,1,n) T.Insert(i),LPP[n-i+1]=T[T.last].len; //反着跑一遍LPP，以i开始的后缀的最长回文前缀

        F(i,1,n) LPS[i]=max(LPS[i],LPS[i-1]);   //以i结尾的前缀的最长回文子串
        D(i,n,1) LPP[i]=max(LPP[i],LPP[i+1]); //以i开头的后缀的最长回文子串

        int ans=0;
        F(i,1,n-1) ans=max(ans,LPS[i]+LPP[i+1]);//枚举断点
        printf("%d\n",ans);
    }

    #define Flan void
    Flan IsMyWife()
    {
        int t;cin>>t;
        while(t--)
        {
            Input();
            Soviet();
        }
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w