Skip to Content
CTRL K

Palindrome

Solución

Primero, construimos el árbol palindrómico (palindromic tree)  a partir de la cadena. Hay O(N)\mathcal{O}(N) palíndromos distintos, así que nuestro árbol tendrá O(N)\mathcal{O}(N) nodos.

Además de la información estándar sobre el palíndromo de un nodo que guardamos en él (p. ej. longitud y enlace de sufijo), guardamos la cantidad de veces que el palíndromo de cada nodo fue el sufijo máximo. Sea CiC_i este número para el ii-ésimo nodo.

Como el palíndromo de cada nodo es una subcadena de los palíndromos de los nodos de su subárbol, la suma de CiC_i en el subárbol del nodo ii nos da la cantidad de ocurrencias del palíndromo del nodo ii en la cadena.

Luego podemos hacer un DFS para hallar la cantidad de ocurrencias de cada palíndromo distinto en la cadena y después simplemente revisar cuál tiene el mayor valor de ocurrencias.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

Complejidad de memoria: O(N)\mathcal{O}(N)

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
 
struct Node {
	int nxt[26], sufflink;
	ll len, cnt;
	vector<int> edges;
} tree[303030];
 
string s;
int suff, num;
ll ans = 0;
 
void add_letter(int pos) {
	int curr = suff, curr_len = 0;
	int letter = s[pos] - 'a';
 
	while (true) {
		curr_len = tree[curr].len;
		if (pos - 1 - curr_len > -1 && s[pos - 1 - curr_len] == s[pos]) break;
		curr = tree[curr].sufflink;
	}
	if (tree[curr].nxt[letter]) {
		suff = tree[curr].nxt[letter];
		tree[suff].cnt++;
		return;
	}
 
	suff = ++num;
	tree[num].len = tree[curr].len + 2;
	tree[num].cnt = 1;
	tree[curr].nxt[letter] = num;
 
	if (tree[num].len == 1) {
		tree[num].sufflink = 2;
		tree[2].edges.push_back(num);
		return;
	}
 
	while (true) {
		curr = tree[curr].sufflink;
		curr_len = tree[curr].len;
		if (pos - 1 - curr_len > -1 && s[pos - 1 - curr_len] == s[pos]) {
			tree[num].sufflink = tree[curr].nxt[letter];
			tree[tree[curr].nxt[letter]].edges.push_back(num);
			break;
		}
	}
}
 
void init() {
	num = 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);
}
 
void dfs(int node = 1) {
	for (int i : tree[node].edges) {
		dfs(i);
		tree[node].cnt += tree[i].cnt;
	}
	ans = max(ans, tree[node].len * tree[node].cnt);
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> s;
	init();
	FOR(i, 0, s.size()) add_letter(i);
	dfs();
	cout << ans;
	return 0;
}
Fundamentos