Submission #1093971

#TimeUsernameProblemLanguageResultExecution timeMemory
1093971Trisanu_DasPalindromes (APIO14_palindrome)C++17
100 / 100
29 ms36356 KiB
#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
const int N = 300000 + 10;
 
int tree[N][26];
int idx, len[N], link[N], cnt[N], t;
string s;
long long oc[N];
 
void add(int p) {
	while (s[p - len[t] - 1] != s[p])t = link[t];
	int x = link[t];
	int c = s[p] - 'a';
	while (s[p - len[x] - 1] != s[p])x = link[x];
	if (tree[t][c] == 0){
		tree[t][c] = ++idx;
		len[idx] = len[t] + 2;
		link[idx] = len[idx] == 1 ? 2 : tree[x][c];
		oc[idx]++;
	}
	else oc[tree[t][c]]++;
	t = tree[t][c];
}
 
int main() {
	len[1] = -1, link[1] = 1;
	len[2] = 0, link[2] = 1;
	idx = t = 2;
	cin >> s;
	s = '$' + s;
	for (int i = 1; i < (int)s.size(); i++)add(i);
	long long ans = 0;
	vector<bool>fre(idx + 1, 0);
	for (int i = idx; i >= 3; --i)  {
		oc[link[i]] += oc[i];
		ans = max(ans, (1ll * len[i] * oc[i]));
	}
	cout << ans << "\n";
 
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...