Submission #1166525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166525		Gurban	Palindromes (APIO14_palindrome)	C++20	100 / 100	66 ms	71116 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int maxn=3e5+5;

string s;

struct Node {
	int nxt[26];
	int len;
	int sufflink;
	int cnt;
	vector<int>edges;
};

Node tree[maxn];
int suff;
int sz;

void addLetter(int pos){

	int let = s[pos] - 'a';
	
	int curr = suff;
	while(1){
		if(pos - tree[curr].len - 1 >= 0 and s[pos - tree[curr].len - 1] == s[pos]) break;
		curr = tree[curr].sufflink;
	}

	if(tree[curr].nxt[let]){
		suff = tree[curr].nxt[let];
		tree[suff].cnt++;
		return;
	}

	suff = ++sz;
	tree[curr].nxt[let] = suff;
	tree[suff].len = tree[curr].len + 2;
	tree[suff].cnt = 1;

	if(tree[suff].len == 1){
		tree[suff].sufflink = 2;
		tree[2].edges.push_back(suff);
		return;
	}

	while(1){
		curr = tree[curr].sufflink;
		if(pos - tree[curr].len - 1 >= 0 and s[pos - tree[curr].len - 1] == s[pos]){
			tree[suff].sufflink = tree[curr].nxt[let];
			tree[tree[suff].sufflink].edges.push_back(suff);
			break;
		}
	}
}

void init(){
	sz = 2;
	suff = 2;
	tree[1].len = -1;
	tree[1].sufflink = 1;

	tree[2].len = 0;
	tree[2].sufflink = 1;
	
	tree[1].edges.push_back(2);
}

ll ans;

void dfs(int nd){

	for(auto i : tree[nd].edges){
		dfs(i);
		tree[nd].cnt += tree[i].cnt;
	}
	ans = max(ans, 1ll * tree[nd].cnt * tree[nd].len);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> s;
	int len = (int)s.size();

	init();

	for(int i = 0;i < len;i++){
		addLetter(i);
	}

	dfs(1);
	cout<<ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27