记录编号	381172	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2014] Palindromes	最终得分	100
用户昵称	__stdcall	是否通过	通过
代码语言	C++	运行时间	3.776 s
提交时间	2017-03-11 08:32:05	内存使用	37.20 MiB

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cctype>

using namespace std;
typedef long long ll;
const int MAXN = 300010, LOGN = 20;

int n;
char str[MAXN];
int sas[MAXN], san;
int mas[MAXN<<1], man;

namespace SA {
	int sa[MAXN], rk[MAXN], ht[MAXN];
	int tmp1[MAXN], tmp2[MAXN], cnt[MAXN];
	int minv[MAXN][LOGN], logn[MAXN];
	void solve( int m ) {
		int *x = tmp1, *y = tmp2;
		for( int i = 0; i < m; ++i ) cnt[i] = 0;
		for( int i = 0; i < san; ++i ) ++cnt[ x[i] = sas[i] ];
		for( int i = 1; i < m; ++i ) cnt[i] += cnt[i-1];
		for( int i = san-1; i >= 0; --i ) sa[--cnt[x[i]]] = i;
		for( int k = 1; k <= san; k <<= 1 ) {
			int p = 0;
			for( int i = san-k; i < san; ++i ) y[p++] = i;
			for( int i = 0; i < san; ++i ) if( sa[i] >= k ) y[p++] = sa[i]-k;
			for( int i = 0; i < m; ++i ) cnt[i] = 0;
			for( int i = 0; i < san; ++i ) ++cnt[x[i]];
			for( int i = 1; i < m; ++i ) cnt[i] += cnt[i-1];
			for( int i = san-1; i >= 0; --i ) sa[--cnt[x[y[i]]]] = y[i];
			swap(x,y), x[sa[0]] = 0, p = 1;
			for( int i = 1; i < san; ++i )
				x[sa[i]] = y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k] ? p-1 : p++;
			if( p == san ) break;
			m = p;
		}
		for( int i = 0; i < san; ++i ) rk[i] = x[i];
		int k = 0;
		for( int i = 0; i < san; ++i ) {
			if( k ) --k;
			if( !rk[i] ) continue;
			int j = sa[rk[i]-1];
			while( sas[i+k] == sas[j+k] ) ++k;
			ht[rk[i]] = minv[rk[i]][0] = k;
		}
		for( int k = 1; (1<<k) <= san; ++k )
			for( int i = 0; i+(1<<k) <= san; ++i )
				minv[i][k] = min( minv[i][k-1], minv[i+(1<<(k-1))][k-1] );
		k = 0;
		for( int i = 1; i <= san; ++i ) {
			if( (1<<(k+1)) <= i ) ++k;
			logn[i] = k;
		}
	}
	int qmin( int l, int r ) {
		int k = logn[r-l+1];
		return min( minv[l][k], minv[r+1-(1<<k)][k] );
	}
}

void input() {
	scanf( "%s", str ), n = strlen(str);
    man = 0;
	for( int i = 0; i < n; ++i ) {
		sas[i] = str[i];
		mas[man++] = '#', mas[man++] = str[i];
	}
	sas[n] = 0, san = n+1;
	mas[man++] = '#';
	SA::solve(128);
}

ll ans = 1;
int rd[MAXN<<1];
void update( int p, int k ) {
	using namespace SA;
    p = rk[p];
	int LL = 0, LR = p;
	while( LL < LR ) {
		int mid = (LL+LR)>>1;
		if( qmin(mid+1,p) >= k ) LR = mid;
		else LL = mid+1;
	}
	int RL = p, RR = san-1;
	while( RL < RR ) {
		int mid = (RL+RR+1)>>1;
		if( qmin(p+1,mid) >= k ) RL = mid;
		else RR = mid-1;
	}
	ans = max( ans, ll(k)*(RL-LL+1) );
}
int cnt[26] = {0};
void manacher() {
	int mx = 0, p = 0;
	for( int i = 0; i < man; ++i ) {
		if( i < mx ) rd[i] = min( rd[2*p-i], mx-i );
		else rd[i] = 1;
		while( i+rd[i] < man && i-rd[i] >= 0 && mas[i+rd[i]] == mas[i-rd[i]] ) {
			if( islower( mas[i-rd[i]] ) ) update( (i-rd[i])/2, rd[i]+1 );
			++rd[i];
		}
		if( i+rd[i] > mx ) mx = i+rd[i], p = i;
	}
	for( int i = 0; i < n; ++i )
		ans = max( ans, (ll)++cnt[str[i]-'a'] );
	printf( "%lld\n", ans );
}

int main() {
	freopen( "apio2014_palindrome.in", "r", stdin );
	freopen( "apio2014_palindrome.out", "w", stdout );
	input(), manacher();
	return 0;
}