[APIO2014]回文串

https://www.luogu.org/problemnew/show/P3649

题目描述

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

对于给你的这个字符串

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

abacaba

输出样例#1：

输入样例#2：

www

输出样例#2：

说明

【样例解释1】

用 |

一个字符串

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

这个样例中，有

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

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

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

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

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

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

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 1000005
 9 #define rep(k,i,j) for(int k=i;k<j;k++)
10 typedef long long ll;
11 typedef unsigned long long ull;
12 
13 const int MAXN = 300005 ;
14 const int N = 26 ;
15 
16 struct Palindromic_Tree {
17     int next[MAXN][N] ;///next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成
18     int fail[MAXN] ;///fail指针，失配后跳转到fail指针指向的节点
19     int cnt[MAXN] ;
20     int num[MAXN] ;
21     int len[MAXN] ;///len[i]表示节点i表示的回文串的长度
22     int S[MAXN] ;///存放添加的字符
23     int last ;///指向上一个字符所在的节点，方便下一次add
24     int n ;///字符数组指针
25     int p ;///节点指针
26 
27     int newnode ( int l ) {///新建节点
28         for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ;
29         cnt[p] = 0 ;
30         num[p] = 0 ;
31         len[p] = l ;
32         return p ++ ;
33     }
34 
35     void init () {///初始化
36         p = 0 ;
37         newnode (  0 ) ;
38         newnode ( -1 ) ;
39         last = 0 ;
40         n = 0 ;
41         S[n] = -1 ;///开头放一个字符集中没有的字符，减少特判
42         fail[0] = 1 ;
43     }
44 
45     int get_fail ( int x ) {///和KMP一样，失配后找一个尽量最长的
46         while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
47         return x ;
48     }
49 
50     void add ( int c ) {
51         c -= 'a' ;
52         S[++ n] = c ;
53         int cur = get_fail ( last ) ;///通过上一个回文串找这个回文串的匹配位置
54         if ( !next[cur][c] ) {///如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
55             int now = newnode ( len[cur] + 2 ) ;///新建节点
56             fail[now] = next[get_fail ( fail[cur] )][c] ;///和AC自动机一样建立fail指针，以便失配后跳转
57             next[cur][c] = now ;
58             num[now] = num[fail[now]] + 1 ;
59         }
60         last = next[cur][c] ;
61         cnt[last] ++ ;
62     }
63 
64     void count () {
65         for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
66         ///父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
67     }
68 };
69 
70 int main(){
71     #ifndef ONLINE_JUDGE
72       //  freopen("input.txt","r",stdin);
73     #endif
74     std::ios::sync_with_stdio(false);
75     string str;
76     Palindromic_Tree pt;
77     pt.init();
78     cin>>str;
79     for(int i=0;i<str.length();i++) pt.add(str[i]);
80     ll ans=0;
81     pt.count();
82     for(int i=2;i<=pt.p;i++){
83         ans=max(ans,1LL*pt.cnt[i]*pt.len[i]);
84     }
85     cout<<ans<<endl;
86 }

View Code