Skip to Content
CTRL K

2012 - Prefixuffix

Explicación

Nos dan un string ss de longitud nn. Debemos elegir un prefijo UU y un sufijo U′U' de la misma longitud tales que:

  • Sean cíclicamente equivalentes.
  • No se solapen en el string original.
  • Su longitud sea máxima.

Si no existiera la condición de equivalencia cíclica, el problema se reduciría a hallar el prefijo más largo que también es un sufijo sin solaparse. Esta es una aplicación clásica de la función prefijo de KMP.

Sin embargo, como se permite la equivalencia cíclica, el prefijo y el sufijo pueden coincidir después de una rotación, así que debemos detectar esas coincidencias de forma eficiente. Esto se resuelve usando hash rolling para comparar subcadenas rápidamente.

Visualizar el requisito

Podemos pensar en la estructura del string de la siguiente forma:

Index:  0       i                 n-i-L    n-i      n
String: |---U---|---V---| . . . . . |---V---|---U---|
Length:     i       L                   L       i

Aquí:

  • UU es el prefijo que debe coincidir con el sufijo.
  • VV es un segmento del medio que aparece a ambos lados del centro.
  • El prefijo y el sufijo no deben solaparse, así que 2i≤n2i \le n.
  • Las partes del medio VV también deben coincidir para satisfacer la condición de rotación cíclica.

Así la longitud candidata final queda i+Li + L.

Idea del algoritmo

Primero computamos la función prefijo (pi) usando KMP. Esto da todas las longitudes posibles de bordes prefijo = sufijo del string.

A continuación debemos tratar la parte de rotación cíclica. Para esto computamos un arreglo auxiliar best[i] que guarda la longitud máxima LL tal que:

  • la subcadena s[i…i+L−1]s[i \dots i+L-1]
  • coincide con la subcadena s[n−i−L…n−1−i]s[n-i-L \dots n-1-i]

Esta comparación debe ser rápida porque ocurre muchas veces. Por eso usamos hash rolling para que cada comparación de subcadenas tome tiempo O(1)O(1).

Llenamos best[i] de derecha a izquierda:

  • Empezamos con best[i] = best[i+1] + 2.
  • Lo reducimos hasta que las dos subcadenas coincidan y los segmentos no se solapen.

Por último:

  1. Empezamos con ans = best[0].
  2. Iteramos sobre todas las longitudes de borde usando la función prefijo.
  3. Si una longitud de borde ii cumple 2i≤n2i \le n, actualizamos ans=max⁡(ans,i+best[i])ans = \max(ans, i + best[i]).

Esto combina efectivamente:

  • KMP para enumerar candidatos válidos prefijo–sufijo.
  • Hash rolling para verificar la estructura de rotación cíclica de forma eficiente.

El resultado es la longitud máxima válida que satisface todas las condiciones.

Implementación

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

 
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1e6 + 5;
const long long BASE = 31;
const long long MOD = 998244353;
 
// BeginCodeSnip{KMP and Rolling Hash}
long long normalize(long long x) {
	x %= MOD;
	if (x < 0) x += MOD;
	return x;
}
 
vector<int> prefix_function(const string &s) {
	int n = s.size();
	vector<int> pi(n);
 
	for (int i = 1; i < n; i++) {
		int j = pi[i - 1];
 
		while (j > 0 && s[i] != s[j]) { j = pi[j - 1]; }
 
		if (s[i] == s[j]) j++;
 
		pi[i] = j;
	}
 
	return pi;
}
 
struct RollingHash {
	vector<long long> pref;
	vector<long long> power;
 
	RollingHash(const string &s) {
		int n = s.size();
		pref.assign(n + 1, 0);
		power.assign(n + 1, 1);
 
		for (int i = 0; i < n; i++) {
			pref[i + 1] = normalize(pref[i] * BASE + s[i]);
			power[i + 1] = normalize(power[i] * BASE);
		}
	}
 
	long long get(int l, int r) {
		return normalize(pref[r + 1] - pref[l] * power[r - l + 1]);
	}
};
// EndCodeSnip
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n;
	string s;
 
	cin >> n >> s;
 
	RollingHash hasher(s);
	vector<int> pi = prefix_function(s);
 
	vector<int> best(n);
 
	for (int i = n / 2 - 1; i >= 0; --i) {
		best[i] = best[i + 1] + 2;
 
		while (best[i] > 0) {
			int len = best[i];
 
			if (i + len - 1 >= n - i - len ||
			    hasher.get(i, i + len - 1) != hasher.get(n - i - len, n - 1 - i))
				best[i]--;
			else break;
		}
	}
 
	int ans = best[0];
 
	for (int i = pi[n - 1]; i > 0; i = pi[i - 1])
		if (i * 2 <= n) ans = max(ans, i + best[i]);
 
	cout << ans << '\n';
 
	return 0;
}
Fundamentos