bzoj 3676: [Apio2014]回文串 回文自动机

xiaoxiao2021-02-28  24

bzoj 3676: [Apio2014]回文串

Description

考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出 现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最 大出现值。

Input

输入只有一行,为一个只包含小写字母(a -z)的非空字符串s。

Output

输出一个整数,为逝查回文子串的最大出现值。

Sample Input

【样例输入l】 abacaba 【样例输入2] www

Sample Output

【样例输出l】 7 【样例输出2] 4

HINT

一个串是回文的,当且仅当它从左到右读和从右到左读完全一样。 在第一个样例中,回文子串有7个:a,b,c,aba,aca,bacab,abacaba,其中: ● a出现4次,其出现值为4:1:1=4 ● b出现2次,其出现值为2:1:1=2 ● c出现1次,其出现值为l:1:l=l ● aba出现2次,其出现值为2:1:3=6 ● aca出现1次,其出现值为1=1:3=3 ●bacab出现1次,其出现值为1:1:5=5 ● abacaba出现1次,其出现值为1:1:7=7 故最大回文子串出现值为7。 【数据规模与评分】 数据满足1≤字符串长度≤300000。

分析

回文自动机裸题 好像可以用manacher+后缀自动机做 回文自动机的算法学习:Palindromic Tree——回文树【处理一类回文串问题的强力工具】 没办法写得更好了。

代码

/************************************************************** Problem: 3676 User: 2014lvzelong Language: C++ Result: Accepted Time:752 ms Memory:37616 kb ****************************************************************/ #include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<cmath> using namespace std; const int N = 310000; long long ans; int len[N], f[N], a[N], val[N], ch[N][26], last, sz, n; void PDT_pre() { f[last = sz = 0] = 1; len[++sz] = a[n = 0] = -1; } void Extend(int c) { a[++n] = c; int p, np, x; for(p = last; a[n - len[p] - 1] != a[n]; p = f[p]) ; if(!ch[p][c]) { len[np = ++sz] = len[p] + 2; for(x = f[p]; a[n - len[x] - 1] != a[n]; x = f[x]) ; f[np] = ch[x][c]; ch[p][c] = np; } ++val[last = ch[p][c]]; } void work() { char ch = getchar(); while(ch < 'a' || ch > 'z') ch = getchar(); for(;ch >= 'a' && ch <= 'z'; ch = getchar()) Extend(ch - 'a'); } int main() { PDT_pre(); work(); for(int i = sz; i >= 2; --i) { val[f[i]] += val[i]; ans = max(ans, 1LL * val[i] * len[i]); } printf("%lld\n", ans); return 0; }
转载请注明原文地址: https://www.6miu.com/read-1600058.html

最新回复(0)