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

Problem

BZOJ3676【APIO2014】回文串

Time Limit: $20 Sec$
Memory Limit: $128 MB$

Description

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

Input

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

Output

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

Sample Input

Input $1$

abacaba

Input $2$

www

Sample Output

Output $1$

7

Output $2$

4

HINT

一个串是回文的，当且仅当它从左到右读和从右到左读完全一样。
在第一个样例中，回文子串有$7$个：$a$，$b$，$c$，$aba$，$aca$，$bacab$，$abacaba$，其中：

• a出现$4$次，其出现值为$4$：$4\times 1=4$
• b出现$2$次，其出现值为$2$：$2\times 1=2$
• c出现$1$次，其出现值为$1$：$1\times 1=1$
• aba出现$2$次，其出现值为$6$：$2\times 3=6$
• aca出现$1$次，其出现值为$3$：$1\times 3=3$
• bacab出现$1$次，其出现值为$5$：$1\times 5=5$
• abacaba出现$1$次，其出现值为$7$：$1\times 7=7$

故最大回文子串出现值为$7$。
数据规模与评分
数据满足 $1\le 字符串长度\le 3\times 10^5$。

标签：回文自动机

Solution

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

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;
}