BZOJ3676【APIO2014】回文串 <回文自动机>

Problem

BZOJ3676【APIO2014】回文串

Time Limit:
Memory Limit:

Description

给你一个由小写拉丁字母组成的字符串 。我们定义 的一个子串的存在值为这个子串在 中出现的次数乘以这个子串的长度。
对于给你的这个字符串 ，求所有回文子串中的最大存在值。

Input

输入只有一行，为一个只包含小写字母的非空字符串 。

Output

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

Sample Input

Input

abacaba

Input

www

Sample Output

Output

7

Output

4

HINT

一个串是回文的，当且仅当它从左到右读和从右到左读完全一样。
在第一个样例中，回文子串有个：，，，，，，，其中：

• a出现次，其出现值为：
• b出现次，其出现值为：
• c出现次，其出现值为：
• aba出现次，其出现值为：
• aca出现次，其出现值为：
• bacab出现次，其出现值为：
• abacaba出现次，其出现值为：

故最大回文子串出现值为。
数据规模与评分
数据满足 。

标签：回文自动机

Solution

回文自动机建出来直接统计答案。
具体回文自动机讲解参见 的博客。

Code

#include <bits/stdc++.h>
#define DICNUM 26
#define MAX_N 300000
using namespace std;
typedef long long lnt;
char s[MAX_N+5];	int cnt, trie[MAX_N+5][DICNUM], fail[MAX_N+5], end[MAX_N+5], len[MAX_N+5];
int newnode(int l) {len[++cnt] = l;	return cnt;}
void init() {fail[0] = newnode(-1), s[0] = '$';}
int getf(int x, int l) {while (s[l-len[x]-1]^s[l]) x = fail[x];	return x;}
int main() {
    scanf("%s", s+1), init();	int n = (int)strlen(s+1);
    for (int i=1, x=s[1]-'a', pre=0, cur=getf(pre,1); i<=n; end[pre=trie[cur][x]]++, x=s[++i]-'a', cur=getf(pre,i))
        if (!trie[cur][x]) newnode(len[cur]+2), fail[cnt] = trie[getf(fail[cur], i)][x], trie[cur][x] = cnt;
    for (int i = cnt; i; i--) end[fail[i]] += end[i];	lnt ans = 0;
    for (int i = 1; i <= cnt; i++) ans = max(ans, 1LL*len[i]*end[i]);
    return printf("%lld", ans), 0;
}