Template

Una plantilla de $S$ es a la vez un prefijo y un sufijo de $S$. Esto sugiere que deberíamos usar KMP.

Si $T$ es una plantilla de $S$ y $U$ es una plantilla de $T$, entonces $U$ también es una plantilla de $S$.

Primero, usamos KMP para computar la función prefijo $\pi$ de $S$. La plantilla más corta de $S$ es o bien $S$ mismo o la plantilla más corta de $S[0 : \pi[|S| - 1]]$.

¡No hay que tener miedo de usar KMP otra vez!

Complejidad temporal: $\mathcal O(N \log N)$.

Primero computamos la función prefijo $\pi$ de $S$ usando KMP.

Si $2\pi[i - 1] \geq i$, entonces $S[0 : i]$ nunca será la plantilla más corta de $S$ porque sabemos que $S[0 : \pi[i - 1]]$ es una plantilla de $S[0 : i]$.

¡Esto significa que solo tenemos $\mathcal O(\log N)$ plantillas candidatas que comprobar! Luego podemos usar KMP de nuevo sobre cada candidata y verificar si el “hueco” máximo entre coincidencias es suficientemente pequeño.

#include <bits/stdc++.h>
using namespace std;
 
string s;
int p[500000];
 
int shortest_template(int n) {
	if (!p[n - 1]) return n;
	if (p[n - 1] * 2 >= n) return shortest_template(p[n - 1]);
	int cand = shortest_template(p[n - 1]);
	for (int i = 0, j = 0, curr = -1; i < n; i++) {
		while (j && (j == cand || s[i] != s[j])) j = p[j - 1];
		if (s[i] == s[j]) j++;
		if (j == cand) curr = i;
		if (i - curr >= cand) return n;
	}
	return cand;
}
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> s;
	int n = s.size();
	for (int i = 1; i < n; i++) {
		p[i] = p[i - 1];
		while (p[i] && s[i] != s[p[i]]) p[i] = p[p[i] - 1];
		if (s[i] == s[p[i]]) p[i]++;
	}
	cout << shortest_template(n);
	return 0;
}

Complejidad temporal: $\mathcal O(N)$.

Primero computamos la función prefijo $\pi$ de $S$ usando KMP. Mientras hacemos esto, también construimos un árbol donde el padre del nodo $(i + 1)$ es $\pi[i]$ para cada $0 \leq i < N$.

Observemos que el subárbol del nodo $i$ es el conjunto de todas las posiciones $j$ donde $S[0 : i] = S[j - i : j]$.

Esto significa que podemos recorrer el árbol hacia arriba desde el nodo $N$ y llevar la cuenta de los nodos en el subárbol del nodo actual (usando una lista enlazada).

Para comprobar si el nodo actual funciona, simplemente verificamos si los huecos entre posiciones en el subárbol son suficientemente pequeños. Podemos llevar la cuenta de estos huecos manteniendo un máximo global que actualizamos cada vez que borramos un nodo de la lista enlazada.

#include <bits/stdc++.h>
using namespace std;
 
const int MX = 5e5 + 5;
 
string s;
int p[MX], mx_gap = 1, ans, prv[MX], nxt[MX];
int graph[MX];
bool visited[MX];
 
int num_child[MX];
int n;
 
void dfs(int node) {
	assert(node <= n);
	visited[node] = true;
	if (node && !visited[p[node - 1]]) {
		dfs(p[node - 1]);
		if (mx_gap <= node) ans = min(ans, node);
	}
	mx_gap = max(mx_gap, nxt[node] - prv[node]);
	nxt[prv[node]] = nxt[node];
	prv[nxt[node]] = prv[node];
	for (int ind = num_child[node]; ind < num_child[node + 1]; ++ind) {
		int i = graph[ind];
		if (!visited[i]) dfs(i);
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> s;
	n = s.size();
	++num_child[0];
	for (int i = 1; i < n; i++) {
		p[i] = p[i - 1];
		while (p[i] && s[i] != s[p[i]]) p[i] = p[p[i] - 1];
		if (s[i] == s[p[i]]) p[i]++;
		++num_child[p[i]];
	}
	for (int i = 1; i <= n + 1; ++i) num_child[i] += num_child[i - 1];
	graph[--num_child[0]] = 1;
	for (int i = 1; i < n; i++) graph[--num_child[p[i]]] = i + 1;
 
	prv[0] = 0, nxt[0] = 1, prv[n] = n - 1, nxt[n] = n;
	for (int i = 1; i < n; i++) prv[i] = i - 1, nxt[i] = i + 1;
	ans = n;
	dfs(n);
	cout << ans;
	return 0;
}

Complejidad temporal: $\mathcal O(N)$.

Primero computamos la función prefijo $\pi$ de $S$ usando KMP.

Luego resolvemos el siguiente problema de forma recursiva: dado un string, ¿cuál es la longitud de su plantilla más corta? Podemos hacerlo así:

1. Hallar la respuesta para el prefijo propio más largo del string que también es un sufijo.
2. Comprobar si esta respuesta también funciona para el string actual.
3. Si lo hace, devolver esa longitud; si no, devolver la longitud del string actual.

Resolveremos cada paso 2 usando DP y otro KMP en tiempo amortizado $\mathcal O(N)$.

Si sabemos dónde coincide una plantilla candidata en un string dado, entonces también podemos comprobar si es una plantilla en tiempo lineal. Sin embargo, esto correrá en tiempo cuadrático en total si no tenemos cuidado.

La observación clave es que, como sabemos que la plantilla candidata también es una plantilla del prefijo propio más largo del string dado, solo necesitamos hacer la DP sobre la parte restante del string. ¡Esto significa que solo necesitamos procesar cada carácter de $S$ en la DP a lo sumo una vez!

Para hallar las coincidencias con la misma eficiencia, ejecutamos KMP sobre el mismo string parcial en cada paso recursivo.

#include <bits/stdc++.h>
using namespace std;
 
string s;
int p[500000];
 
int shortest_template(int n) {
	if (!p[n - 1]) return n;
	int cand = shortest_template(p[n - 1]);
	for (int i = p[n - 1], j = cand, curr = p[n - 1] - 1; i < n; i++) {
		while (j && (j == cand || s[i] != s[j])) j = p[j - 1];
		if (s[i] == s[j]) j++;
 
		if (j == cand) curr = i;
		if (i - curr >= cand) return n;
	}
	return cand;
}
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> s;
	int n = s.size();
	for (int i = 1; i < n; i++) {
		p[i] = p[i - 1];
		while (p[i] && s[i] != s[p[i]]) p[i] = p[p[i] - 1];
		if (s[i] == s[p[i]]) p[i]++;
	}
	cout << shortest_template(n);
	return 0;
}