Búsqueda en strings

Un solo string

Algoritmo de Knuth-Morris-Pratt

Definimos un arreglo $\pi_S$ de tamaño $|S|$ tal que $\pi_S[i]$ es igual a la longitud del sufijo no trivial más largo del prefijo que termina en la posición $i$ que coincide con un prefijo de todo el string. Formalmente,

En otras palabras, para un índice $i$ dado, queremos calcular la longitud de la subcadena más larga que termina en $i$ tal que este string también resulta ser un prefijo de todo el string. Un string que cumple este criterio es el prefijo que termina en $i$; descartaremos esta solución por razones obvias.

Por ejemplo, para $S = \text{``abcabcd"}$, $\pi_S = [0, 0, 0, 1, 2, 3, 0]$, y la función prefijo de $S = \text{``aabaaab"}$ es $\pi_S = [0, 1, 0, 1, 2, 2, 3]$. En el segundo ejemplo, $\pi_S[4] = 2$ porque el prefijo de longitud $2$ ($\text{``aa"}$) es equivalente a la subcadena de longitud $2$ que termina en el índice $4$. De la misma forma, $\pi_S[6] = 3$ porque el prefijo de longitud $3$ ($\text{``aab"}$) es igual a la subcadena de longitud $3$ que termina en el índice $6$. En ambos ejemplos, no hay una subcadena más larga que cumpla estos criterios.

El propósito del algoritmo KMP es calcular de forma eficiente el arreglo $\pi_S$ en tiempo lineal. Supongamos que ya calculamos el arreglo $\pi_S$ para los índices $0\dots i$, y hay que calcular el valor para el índice $i + 1$.

En primer lugar, nótese que entre $\pi_S[i]$ y $\pi_S[i + 1]$, $\pi_S[i + 1]$ puede ser a lo sumo uno mayor. Esto ocurre cuando $S[\pi_S[i]] = S[i + 1]$.

En el ejemplo de arriba, $\pi_S[i] = 5$, lo que significa que el sufijo de longitud $5$ es equivalente a un prefijo de longitud $5$ de todo el string. Sigue que si el carácter en la posición $5$ del string es igual al carácter en la posición $i + 1$, entonces la coincidencia se extiende simplemente en un carácter. Así, $\pi_S[i + 1] = \pi_S[i] + 1 = 6$.

En el caso general, sin embargo, esto no es necesariamente cierto. Es decir, $S[\pi_S[i]] \neq S[i + 1]$. Así, hay que hallar el mayor índice $j < \pi_S[i]$ tal que se cumpla la propiedad de prefijo (es decir, $S[:j - 1] \equiv S[i - j + 1:i]$). Para tal longitud $j$, repetimos el procedimiento del primer ejemplo comparando los caracteres en los índices $j$ e $i + 1$: si son iguales, entonces podemos concluir la búsqueda y asignar $\pi_S[i + 1] = j + 1$; en caso contrario, hallamos el siguiente $j$ más pequeño y repetimos. De hecho, nótese que el primer ejemplo es simplemente el caso en que $j$ empieza como $\pi_S[i]$.

En el segundo ejemplo de arriba, tomamos $j = 2$.

Lo único que queda es poder hallar de forma eficiente todos los $j$ que podríamos necesitar. Para recapitular, si la posición en la que estamos actualmente es $j$, para manejar las transiciones hay que hallar el mayor índice $k$ que cumple la propiedad de prefijo $S[:k - 1] \equiv S[j - k + 1 : j]$. Como $j < i$, este valor es simplemente $\pi_S[j - 1]$, un valor que ya se calculó. Solo queda manejar el caso $j = 0$. Si $S[0] = S[i + 1]$, $\pi_S[i + 1] = 1$; en caso contrario, $\pi_S[i + 1] = 0$.

vector<int> pi(const string &s) {
	int n = (int)s.size();
	vector<int> pi_s(n);
	for (int i = 1, j = 0; i < n; i++) {
		while (j > 0 && s[j] != s[i]) { j = pi_s[j - 1]; }
		if (s[i] == s[j]) { j++; }
		pi_s[i] = j;
	}
	return pi_s;
}

from typing import List
 
 
def pi(s: str) -> List[int]:
	n = len(s)
	pi_s = [0] * n
	j = 0
	for i in range(1, n):
		while j > 0 and s[j] != s[i]:
			j = pi_s[j - 1]
		if s[i] == s[j]:
			j += 1
		pi_s[i] = j
	return pi_s

Afirmación: El algoritmo KMP corre en $\mathcal{O}(n)$ para calcular el arreglo $\pi_S$ sobre un string $S$ de longitud $n$.

Demostración: Nótese que $j$ en realidad no cambia a través de varias iteraciones. Esto se debe a que en la iteración $i$, asignamos $j = \pi_S[i - 1]$. Sin embargo, en la iteración anterior, asignamos $\pi_S[i - 1]$ como $j$. Además, nótese que $j$ es siempre no negativo. En cada iteración de $i$, $j$ solo aumenta en a lo sumo $1$ en el if. Como $j$ permanece no negativo y solo aumenta una cantidad constante por iteración, se sigue que $j$ solo puede disminuir a lo sumo $n$ veces a lo largo de todas las iteraciones de $i$. Como el bucle interno está completamente gobernado por $j$, la complejidad total se amortiza a $\mathcal{O}(n)$. $\blacksquare$

Problemas

Algoritmo Z

Explicación

El algoritmo Z es muy similar a KMP, pero usa una función distinta de $\pi$ y tiene una aplicación interesante diferente del matching de strings.

En lugar de usar $\pi$, usa la función Z. Dada una posición, esta función da la longitud del string más largo que es a la vez prefijo de $S$ y prefijo del sufijo de $S$ que empieza en la posición dada.

Aquí hay algunos ejemplos de cómo puede verse esta función:

• aabxaayaab $\rightarrow$ $Z=[10,1,0,0,2,1,0,3,1,0]$
• aabxaabxcaabxaabxay $\rightarrow$ $Z=[18,1,0,0,4,1,0,0,0,8,1,0,0,5,1,0,0,1,0]$

Veamos más de cerca $Z_9=8$ (indexación desde cero) para el segundo string. El valor de esta posición es $8$ porque ese es el prefijo común más largo entre el string mismo aabxaabxcaabxaabxay y el sufijo que empieza en la posición $9$ aabxaabxay (también indexado desde cero).

Para calcular este arreglo de forma eficiente, mantenemos el intervalo $[l, r]$ tal que $S_{l...r}$ también es un prefijo, es decir, $Z_l=r-l+1$.

Digamos que tenemos una posición $i$ en cualquier lugar de $[l,r]$. Entonces tendríamos estos dos casos:

1. Si $i + Z_{i-l} < r$, sabemos que $Z_i = Z_{i-l}$.
2. En caso contrario, $i + Z_{i-l} \geq r$, lo que significa que la respuesta puede extenderse más allá de $r$. Así, comparamos carácter a carácter a partir de ahí.

Implementación

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

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
vector<int> z_function(const string &s) {
	vector<int> z(s.size());
	z[0] = s.size();
 
	int l = 0;
	int r = 0;
	for (int i = 1; i < s.size(); i++) {
		z[i] = max(0, min(z[i - l], r - i + 1));
		while (i + z[i] < s.size() && s[z[i]] == s[i + z[i]]) {
			l = i;
			r = i + z[i];
			z[i]++;
		}
	}
 
	return z;
}
 
int main() {
	string s;
	cin >> s;
	vector<int> z = z_function(s);
	for (int i = 1; i < s.size(); i++) {
		if (i + z[i] == s.size()) { cout << i << " "; }
	}
	cout << s.size() << endl;
}

from typing import List
 
 
def z_function(s: str) -> List[int]:
	n = len(s)
	z = [0] * n
	z[0] = n
	l, r = 0, 0
	for i in range(1, n):
		z[i] = max(0, min(z[i - l], r - i + 1))
		while i + z[i] < n and s[i + z[i]] == s[z[i]]:
			l = i
			r = i + z[i]
			z[i] += 1
	return z
 
 
s = input()
z = z_function(s)
for i in range(1, len(z)):
	if i + z[i] == len(s):
		print(i, end=" ")
print(len(s))

Palíndromos

Manacher

El algoritmo de Manacher funciona de forma similar al algoritmo Z. Determina el palíndromo más largo centrado en cada carácter.

Denotemos $dp_i$ como el diámetro máximo de un palíndromo centrado en $i$. El algoritmo de Manacher usa los $dp_j$ ya determinados, donde $j < i$, al calcular $dp_i$. La idea principal es que para un palíndromo centrado en $i$ con bordes $left$ y $right$, los valores $dp_j$ ($i < j \le right$) son — probablemente — espejos de los valores $dp_k$ ($left \le k < i$) del lado izquierdo del palíndromo. Probablemente porque para algunos $j$ el palíndromo máximo podría cruzar el borde derecho. De este modo el algoritmo solo considera los centros de palíndromo que podrían llevar a la expansión del palíndromo máximo.

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

#include <bits/stdc++.h>
using namespace std;
 
string menacher(string s) {
	// Preprocesar la entrada para poder manejar palíndromos de longitud par
	string arr;
	for (int i = 0; i < s.size(); i++) {
		arr.push_back('#');
		arr.push_back(s[i]);
	}
	arr.push_back('#');
 
	// dp[i] = diámetro máximo del palíndromo centrado en i
	vector<int> dp(arr.size());
	int left = 0;
	int right = 0;
	int lg_max = 0;
	int idx = 0;
	for (int i = 0; i < arr.size();) {
		// Expandir el palíndromo alrededor de i
		while (left > 0 && right < arr.size() - 1 && arr[left - 1] == arr[right + 1]) {
			left--;
			right++;
		}
 
		// Actualizar el diámetro
		dp[i] = right - left + 1;
 
		if (lg_max < dp[i]) {
			lg_max = dp[i];
			idx = i;
		}
 
		/*
		 * Ya calculamos los valores del intervalo [left, i].
		 * Los valores del lado derecho del palíndromo [i+1, right] serán
		 * los mismos que los del lado izquierdo excepto cuando algunos
		 * palíndromos se salen del palíndromo actual [left, right].
		 */
		int new_center = right + (i % 2 == 0 ? 1 : 0);
		for (int j = i + 1; j <= right; j++) {
			/*
			 * i - (j - i) representa el espejo de j en el lado izquierdo del
			 * palíndromo. Es posible que el espejo izquierdo de j se salga
			 * del palíndromo actual: cruza el borde izquierdo. Para
			 * evitar tomar la respuesta incorrecta, tomar el mínimo del
			 * espejo izquierdo de j y el diámetro del palíndromo centrado
			 * en j que termina en right.
			 */
			dp[j] = min(dp[i - (j - i)], 2 * (right - j) + 1);
 
			// Actualizar el diámetro máximo
			if (lg_max < dp[i]) {
				lg_max = dp[i];
				idx = i;
			}
 
			/*
			 * Si el palíndromo centrado en j llega al borde derecho del
			 * palíndromo actual, podría ir aún más allá.
			 * Considerando esto, hacer new_center = j.
			 */
			if (j + dp[i - (j - i)] / 2 == right) {
				new_center = j;
				break;
			}
		}
 
		// Moverse a new_center y actualizar los bordes izquierdo y derecho.
		i = new_center;
		right = i + dp[i] / 2;
		left = i - dp[i] / 2;
	}
 
	int lg = 0;
	string ans = "";
	for (int j = idx - dp[idx] / 2; j <= idx + dp[idx] / 2; j++) {
		if (arr[j] != '#') { ans.push_back(arr[j]); }
	}
 
	return ans;
}
 
int main() {
	string s;
	cin >> s;
	cout << menacher(s) << endl;
}

Árbol palindrómico

Un árbol palindrómico (Palindromic Tree) es una estructura de datos parecida a un árbol que se comporta de forma similar a KMP. A diferencia de KMP, en el que el único estado vacío es $0$, el árbol palindrómico tiene dos estados vacíos: longitud $0$ y longitud $-1$. Esto se debe a que agregar un carácter a un palíndromo aumenta la longitud en $2$, lo que significa que un palíndromo de un solo carácter debió crearse a partir de un palíndromo de longitud $-1$.

Varios strings

Tries

Un trie es una estructura de datos parecida a un árbol que guarda strings. Cada nodo es un string, y cada arista es un carácter.

La raíz es el string vacío, y cada nodo está representado por los caracteres a lo largo del camino desde la raíz hasta ese nodo. Esto significa que todo prefijo de un string es un ancestro del nodo de ese string.

#include <bits/stdc++.h>
using namespace std;
 
const int NMAX = 5e3;
const int WMAX = 1e6;
const int MOD = 1e9 + 7;
 
int trie[WMAX][26];
int node_count;
bool stop[WMAX];
 
/** Agrega una palabra nueva al trie. */
void insert(string word) {
	// El nodo 0 tiene 26 hijos: de a a z.
	int node = 0;
	for (char c : word) {
		// Si no existe un nodo con el carácter actual, crear uno.
		if (trie[node][c - 'a'] == 0) { trie[node][c - 'a'] = ++node_count; }
		// Bajar por el camino en el trie.
		node = trie[node][c - 'a'];
	}
	// Marcar el nodo final para saber que es una palabra del diccionario
	stop[node] = true;
}
 
int main() {
	string s;
	int n;
	cin >> s >> n;
 
	for (int i = 0; i < n; i++) {
		string word;
		cin >> word;
		insert(word);
	}
 
	// dp[i] = de cuántas formas se puede formar s[i..s.size()]?
	vector<int> dp(s.size() + 1);
	dp[s.size()] = 1;
	for (int i = s.size() - 1; i >= 0; i--) {
		int node = 0;
 
		// Comprobar si s[i..j] es una palabra del diccionario.
		for (int j = i; j < s.size(); j++) {
			// Si el carácter no existe en el trie, cortar.
			if (trie[node][s[j] - 'a'] == 0) { break; }
			// Moverse al siguiente nodo.
			node = trie[node][s[j] - 'a'];
 
			/*
			 * Si stop[node] es true entonces es el final de una palabra.
			 * Sumar a dp[i] la cantidad de formas en que se puede formar
			 * s[j+1...s.size()].
			 */
			if (stop[node]) { dp[i] = (dp[i] + dp[j + 1]) % MOD; }
		}
	}
 
	cout << dp[0] << endl;
}

Aho-Corasick

El algoritmo de Aho-Corasick guarda las palabras patrón en una estructura trie, descrita arriba. Usa el trie para transicionar de un estado a otro. Similar al algoritmo KMP, queremos reutilizar la información que ya procesamos.

Un enlace de sufijo (suffix link) o enlace de fallo (failure link) de un nodo $u$ es una arista especial que apunta al sufijo propio más largo del string correspondiente al nodo $u$. Los enlaces de sufijo de la raíz y de todos sus hijos inmediatos apuntan al nodo raíz. Para todos los demás nodos $u$ con padre $p$ y letra $c$ en la arista $p \rightarrow u$, el enlace de sufijo se puede calcular siguiendo el enlace de fallo de $p$ y transicionando a la letra $c$ desde ahí.

Mientras procesa el string $S$, el algoritmo mantiene el nodo actual en el trie tal que la palabra formada en el nodo es igual al sufijo más largo que termina en $i$.

Por ejemplo, al transicionar de $i$ a $i+1$ en $S$ solo hay dos opciones:

1. Si $node$ tiene una arista saliente con letra $S_{i+1}$, entonces bajar por esa arista.
2. En caso contrario, seguir el enlace de fallo de $S_i$ y transicionar a la letra $S_{i+1}$ desde ahí.

La imagen de abajo muestra cómo se ve la estructura para las palabras $[a, ag, c, caa, gag, gc, gca]$.

Hay un caso especial cuando algunas palabras son subcadenas de otras palabras de la lista. Esto podría causar problemas según la implementación. Los enlaces de diccionario  pueden resolver este problema. Actúan como enlaces de sufijo que apuntan al primer sufijo que también es una palabra de la lista. El código de abajo construye la estructura usando un BFS.

Complejidad temporal: $\mathcal{O}(m\sigma)$ — donde $m$ es el tamaño del alfabeto y $\sigma$ el tamaño del alfabeto

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX_N = 6e5;
const int SIGMA = 26;
 
int n;
string s;
// El número de nodos en el trie
int nodes = 1;
int trie[MAX_N][SIGMA];
int fail[MAX_N];  // fail[u] = el enlace de fallo del nodo
int seen[MAX_N];  // comprobar si un nodo se visitó en el trie
int ans[MAX_N];   // ans[i] = el número de ocurrencias de la palabra i
 
// leaf[node] guarda los índices de las palabras que terminan en node
vector<int> leaf[MAX_N];
vector<int> g[MAX_N];
 
/** Agregar una palabra al trie */
void add_word(const string &word, const int &idx) {
	int node = 1;
	for (char ch : word) {
		if (trie[node][ch - 'a'] == 0) { trie[node][ch - 'a'] = ++nodes; }
		node = trie[node][ch - 'a'];
	}
	leaf[node].push_back(idx);
}
 
/** BFS para construir los enlaces de fallo y de sufijo */
void build() {
	queue<int> q;
	int node = 1;
	fail[node] = 1;
	for (int i = 0; i < SIGMA; i++) {
		if (trie[node][i]) {
			fail[trie[node][i]] = node;
			q.push(trie[node][i]);
		} else {
			trie[node][i] = 1;
		}
	}
 
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		for (int i = 0; i < SIGMA; i++) {
			if (trie[node][i]) {
				fail[trie[node][i]] = trie[fail[node]][i];
				q.push(trie[node][i]);
			} else {
				trie[node][i] = trie[fail[node]][i];
			}
		}
	}
	for (int i = 2; i <= nodes; i++) { g[fail[i]].push_back(i); }
}
 
void search() {
	int node = 1;
	for (char ch : s) {
		node = trie[node][ch - 'a'];
		seen[node]++;
	}
}
 
int dfs(int node) {
	int sol = seen[node];
	for (int son : g[node]) { sol += dfs(son); }
	for (int idx : leaf[node]) { ans[idx] = sol; }
	return sol;
}
 
int main() {
	cin >> s >> n;
 
	vector<string> words(n);
	for (int i = 0; i < n; i++) {
		cin >> words[i];
		add_word(words[i], i);
	}
 
	build();
	search();
	dfs(1);
 
	for (int i = 0; i < n; i++) { cout << (ans[i] ? "YES" : "NO") << '\n'; }
}

Problemas