Description

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

Input

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

Output

输出一个整数，为所有回文子串的最大出现值。

Sample Input1

abacaba

Sample Input2

www

Sample Output1

7

Sample Output2

4

HINT

\(1 \le \mid s \mid \le300000\)

朴素做法：manacher+后缀数组。用manacher求出所有本质不同的回文串，对于每个本质不同的回文串，在后缀数组中二分出它的出现次数。复杂度\(O(nlogn)\)。（参见ZJOI模拟题BYcenbo palindrome）

但是我们有回文自动机（参见：Palindromic Tree——回文树【处理一类回文串问题的强力工具】）。你知道回文自动机能做什么，你就能AC了。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

using namespace std;

typedef long long ll;

#define maxn (300010)

ll ans;

struct pat

{

	int next[maxn][26],fail[maxn],cnt[maxn],len[maxn],s[maxn],last,n,p;

	inline int newnode(int l) { cnt[p] = 0; len[p] = l; return p++; }

	inline void init() { last = n = p = 0; newnode(0); newnode(-1); s[0] = -1; fail[0] = 1; }

	inline int getfail(int x) { while (s[n-len[x]-1] != s[n]) x = fail[x]; return x; }

	inline void add(int c)

	{

		s[++n] = c; int cur = getfail(last);

		if (!next[cur][c])

		{

			int now = newnode(len[cur]+2);

			fail[now] = next[getfail(fail[cur])][c];

			next[cur][c] = now;

		}

		last = next[cur][c]; cnt[last]++;

	}

	inline void count()

	{

		for (int i = p-1;i >= 0;--i) cnt[fail[i]] += cnt[i];

		for (int i = 0;i < p;++i) ans = max(ans,(ll)cnt[i]*len[i]);

	}

}tree;

int main()

{

	freopen("3676.in","r",stdin);

	freopen("3676.out","w",stdout);

	tree.init();

	while (true)

	{

		char ch = getchar();

		if (ch >= 'a'&&ch <= 'z') tree.add(ch-'a');

		else break;

	}

	tree.count(); printf("%lld",ans);

	fclose(stdin); fclose(stdout);

	return 0;

}

巴特西

BZOJ 3676 回文串

Description

Input

Output

Sample Input1

Sample Input2

Sample Output1

Sample Output2

HINT

最新文章

热门文章