BZOJ3676: [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的题目有了回文自动机（回文自动机可以看这篇博客：我是忧郁的“这篇博客”）瞬间变成板子题，代码长度--，代码难度--，正确率+=inf，PAM真的是神器。但是距离熟练运用可能还有一段距离。

大致思路很清晰了，回文自动机统计每一个本质不同回文串的出现次数和长度，复杂度为O（n）。代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 3e5 + 5;

namespace PAM {
	char s[maxn];
	int trie[maxn][26], sum[maxn], fail[maxn], len[maxn];
	int cnt, pos, last;
	void init() {
		cnt = 1, pos = last = 0;
		fail[0] = 1, len[0] = 0, len[1] = -1;
	}
	int getfail(int p) {
		while(s[pos - len[p] - 1] != s[pos])
			p = fail[p];
		return p;
	}
	void add(int x) {
		int id = s[x] - 'a';
		int p = getfail(last);
		if(!trie[p][id]) {
			int now = ++cnt;
			fail[now] = trie[getfail(fail[p])][id];
			trie[p][id] = now;
			
			len[now] = len[p] + 2;
		}
		last = trie[p][id];
		++sum[last];
	}
	void push_up() {
		for(register int i = cnt; i >= 0; --i)
			sum[fail[i]] += sum[i];
	}
	void create() {
		int sl = strlen(s);
		for(register int i = 0; i < sl; ++i)
			pos = i, add(i);
		push_up();
	}
	long long cntans() {
		long long ans = 0;
		for(register int i = 2; i <= cnt; ++i)
			ans = max(ans, 1LL * len[i] * sum[i]);
		return ans;
	}
}

int main() {
	PAM::init();
	scanf("%s", PAM::s);
	PAM::create();
	printf("%lld", PAM::cntans());
}

Rockdu's Blog