P3649 [APIO2014]回文串

题目描述

给你一个由小写拉丁字母组成的字符串

对于给你的这个字符串

输入输出格式

输入格式：

一行，一个由小写拉丁字母（a~z）组成的非空字符串

输出格式：

输出一个整数，表示所有回文子串中的最大存在值。

输入输出样例

输入样例#1：复制

abacaba

输出样例#1：复制

输入样例#2：复制

www

输出样例#2：复制

说明

【样例解释1】

用

一个字符串 $s_1 s_2 dots s_{lvert s vert}s1s2…s∣s∣ 的子串是一个非空字符串 s_i s_{i+1} dots s_jsisi+1…sj，其中 1 leq i leq j leq lvert s vert1≤i≤j≤∣s∣。每个字符串都是自己的子串。$

一个字符串被称作回文串当且仅当这个字符串从左往右读和从右往左读都是相同的。

这个样例中，有

所以回文子串中最大的存在值为

第一个子任务共 8 分，满足

第二个子任务共 15 分，满足

第三个子任务共 24 分，满足

第四个子任务共 26 分，满足

第五个子任务共 27 分，满足

首先可以SA+manacher，但是这是回文树的板子（-。-）

 1 #include"bits/stdc++.h"
 2 using namespace std;
 3 typedef long long ll;
 4 const int nn = 300010;
 5 
 6 char s[300010];
 7 
 8 int fail[nn],len[nn],cnt[nn];
 9 int nxt[nn][26];
10 int S[nn];
11 int tot;
12 int num=1;
13 inline int getfail(int x){
14     for (;S[tot-len[x]-1]!=S[tot];x=fail[x]); return x;
15 }
16 
17 int main()
18 {
19     scanf("%s",s);  int last;
20     int n=strlen(s);   
21     fail[0]=1;len[1]=-1;last=0;tot=0; S[0]=-1;
22     for (register int i=0;i<n;i++)
23     {
24     //    cout<<i<<endl;
25         int c=s[i]-'a'; S[++tot]=c;int cur=getfail(last);
26     //    cout<<123<<endl;
27         if (!nxt[cur][c])
28         {   
29             fail[++num]=nxt[getfail(fail[cur])][c];//顺序
30             nxt[cur][c]=num;
31             len[num]=len[cur]+2;
32             
33         //    cout<<123<<endl;; 
34         }
35          last=nxt[cur][c]; cnt[last]++;
36     }
37     ll ans=0;
38     
39     for (register int i=num;i>=2;i--)cnt[fail[i]]+=cnt[i];
40     for (register int i=num;i>=2;i--)
41     {
42         ans=max(ans,1ll*cnt[i]*len[i]);
43     }
44     
45     printf("%lld",ans);
46  }