# Cadenas (Div. C)
## Hash
### Función Hash
Una función hash le asigna un valor numérico a un objeto (generalmente una cadena). El rango de valores que puede devolver una función hash es finito. Los problemas más comunes en los que usa hash son aquellos en los que hay que comparar cadenas.
Buscamos que una función hash cumpla las siguientes características:
- Que regrese el mismo valor si dos objetos son iguales.
- Que regrese distinto hash con **alta probabilidad** si dos objetos son diferentes. Normalmente, es mayor la cantidad de objetos posibles que puede recibir la función que la cantidad de valores puede regresar, por lo que inevitablemente habrá diferentes objetos asignados al mismo valor.
Una **colisión** ocurre cuando dos objetos diferentes son asignados al mismo valor.
### Algunas posibles funciones hash.
Cuando trabajamos con cadenas, el valor hash se suele obtener en función del [valor ASCII](https://upload.wikimedia.org/wikipedia/commons/2/26/Ascii-codes-table.png) de los carácteres. Veamos algunas funciones hash para cadenas:
#### Suma del valor ASCII.
Definamos la función hash como la suma del valor ASCII de los carácteres:
:::info
:information_source: **Ejemplo**
$f('abc')=97+98+99=294$
$f('fAd*')=102+65+100+42=309$
$f('aad')=97+97+100=294$
$f('bac')=98+97+99=294$
:::
En el ejemplo podemos observar tres colisiones. Como la suma es conmutativa, si dos cadenas contienen el mismo multiconjunto de carácteres, entonces tendrán el mismo valor hash aunque sean diferentes. Por esta razón, esta es una **mala opción**.
#### Suma de valores ASCII por la posición.
Definamos la función hash como la suma del valor ASCII de los carácteres múltiplicada por su posición (índexado en $1$):
:::info
:information_source: **Ejemplo**
$f('abc')=97 \cdot 1+98 \cdot 2+99\cdot 3=590$
$f('fAd*')=102\cdot 1+65\cdot 2+100\cdot 3+42\cdot 4=700$
$f('ab')=97\cdot 1+98\cdot 2=293$
$f('ca')=99\cdot 1+97\cdot 2=293$
:::
Con esta función hash, las cadenas que tengan el mismo multiconjunto de carácteres ya no tendrán el mismo valor necesariamente. Pero aún así, sigue siendo fácil obtener dos cadenas con el mismo hash. También es una **mala opción**.
#### Hash polinomial.
Recordar que un polinomio de grado $n$ es una expresión de la forma $P(x)=a_0+a_1x+a_2x^2+a_3x^3+\dots+a_nx^n$.
Ahora la función hash será un polinomio $P$. Los coeficientes de $P$ serán el valor ASCII de los carácteres, y $x$ tendrá un valor constante.
:::info
:information_source: **Ejemplo**
Si elegimos $x=200$, tenemos que:
$f('abc')=97+98 \cdot 200 + 99 \cdot 200^2=3979697$
$f('fAd*')=102+65\cdot 200+100\cdot 200^2+42\cdot 200^3=340013102$
$f('ab')=97+98\cdot 200=19697$
$f('ca')=99+97\cdot 200=19499$
:::
Si el valor de $x$ elegido es mayor al valor ASCII de todos los carácteres, entonces **todas** las cadenas tendrán un valor hash distinto. Este se justifica debido a que esta función hash es equivalente a hallar el valor de un número dados sus dígitos en base $x$. Esto también se pude demostrar con el algoritmo de la división e inducción: https://math.stackexchange.com/a/2174564
La desventaja de este hash es que puede devolver números muy grandes que no quepan en un `int` o `long long`. A continuación vamos a ver la función hash más usada.
### Hash polinomial módulo $m$
La función hash estará basada en un polinomio como la anterior, pero ahora tomaremos el valor hash módulo un número primo $p$.
:::info
:information_source: **Ejemplo**
Si elegimos $x=200$ y $m=100003$ (un primo), tenemos que:
$f('abc')=(97+98 \cdot 200 + 99 \cdot 200^2) \% 100003=79580$
$f('fAd*')=(102+65\cdot 200+100\cdot 200^2+42\cdot 200^3)\% 100003 =2902$
$f('ab')=(97+98\cdot 200)\%100003=19697$
$f('ca')=(99+97\cdot 200)\%100003=19499$
:::
El rango de valores que puede regresar esta función es $[0,m)$, es decir, sólo hay $m$ valores distintos que puede regresar, así que podrían haber **colisiones**.
Desearíamos que la distribución de valores hash fuera lo más uniforme posible, es decir, que para una cadena **aleatoria**, la probabilidad de que tome un valor $y$, sea el mismo para todas las $y \in [0,m)$. Esto ocurre cuando $gcd(x,m)=1$. En este caso la probabilidad de colisión entre dos cadenas es $\frac{1}{m}$. Para facilitar que se cumpla esta condición, se elige un módulo $m$ primo, y un $x$ tal que $max(c_i)<x<m$.
:::spoiler ¿Por qué es necesario que gcd(x,m)=1?
Si tenemos una cadenas $s$ que empieza con un carácter cuyo valor ASCII es $s_1$, entonces el hash de $s$ sólo puede tomar valores de la forma $(s_1 + xk) \% m$:
$$
\begin{align}
H(s) &= (s_1 + s_1x + s_2x^2 + \dots + s_{|s|}x^{|s|}) \% m \\
&= (s_1 + x(s_1 + s_2x^1 + \dots + s_{|s|}x^{|s|-1})) \% m \\
&= (s_1 + xk) \% m
\end{align}
$$
$(s_1 + xk) \% m$ puede tomar la misma cantidad de valores que toma $xk \% m$. Si $gcd(x,m)=g$, entonces $x(k + \frac{m}{g}) \% m=(xk + x\frac{m}{g}) \% m=(xk + m\frac{x}{g}) \% m=xk \% m$ (el valor de $xk$ se divide en $\frac{m}{g}$ clases de equivalencia), así que $(s_1 + xk) \% m$ puede tomar a lo más $\frac{m}{g}$ valores distintos y la probabilidad de colisión es $\frac{g}{m}$ con una cadena que empiece con $s_1$. Esto también se puede explicar con el orden aditivo modulo $m$.
:::
#### Implementación
La siguiente es la implementación más simple de la función hash polinomial módulo un primo.
``` C++
const int mod = 1e9 + 7; // 10^9 + 7.
const int x = 200;
int H (const string &s) {
int res = 0, xi = 1;
for (int i = 0; i < (int)s.size(); i++) {
res = (res + (long long)s[i] * xi) % mod;
xi = (long long)xi * x % mod;
}
return res;
}
```
Se recomienda usar la implementación de arriba en concursos donde no haya fase de hacking (como competencias ICPC). Como en codeforces es posible hackear soluciones, es preferible utilizar $x$ aleatoria (ya que con $x$ constante es más fácil entontrar una colisión). A continuación está una implementación con $x$ aleatoria:
``` C++
const int mod = 1e9 + 7; // 10^9 + 7.
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randint (int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
int x = randint(256, mod - 1);
int H (const string &s) {
int res = 0, xi = 1;
for (int i = 0; i < (int)s.size(); i++) {
res = (res + (long long)s[i] * xi) % mod;
xi = (long long)xi * x % mod;
}
return res;
}
```
Notar que se utiliza `uniform_int_distribution<T>()` en lugar de `rand()`. Esto es porque el rango de `rand()` es pequeño, como se describe en este blog: https://codeforces.com/blog/entry/61587.
### Hash para subcadenas
La mayoría de problemas de hash en cadenas requieren encontrar el valor hash no sólo de una cadena completa, si no también de algunas de sus subcadenas. Seguiremos utilizando la función hash polinomial módulo $m$.
Digamos que la cadena $s$ es la secuencia de carácteres $s_1s_2s_3s_4\dots s_{|s|}$. El valor hash de su subcadena $s[l,r]$ debería ser $s_l+s_{l+1}x^1+s_{l+2}x^2+\dots+s_rx^{r-l}$.
:::info
:information_source: **Ejemplo**
Si $s='abacaba'$, $x=200$ y $m=100003$ (un primo):
$f(s[2,2])=f('b')=(98) \% 100003=98$
$f(s[3,6])=f('acab')=(97 + 99 \cdot 200 + 97 \cdot 200^2 + 98 \cdot 200^3) \% 100003 = 76263$
$f(s[5,7])=f('aba')=(97+98\cdot 200+97\cdot 200^2)\%100003=99583$
$f(s[1,3])=f('aba')=(97+98\cdot 200+97\cdot 200^2)\%100003=99583$
$f(s[1,7])=f('abacaba')=(97+98\cdot 200+97\cdot 200^2+99 \cdot 200^3 + 97 \cdot 200^4 + 98 \cdot 200^5+97 \cdot 200^6)\%100003=35217$
:::
¿Cómo sacar el valor de $f(s[l,r])$ rápido? Utilizaremos la técnica de suma de prefijos.
Notemos que los términos del polinomio para calcular $f(s[l,r])$ son una *subsecuencia contigua* del polinomio de $f(s)$, formada por los términos desde la posición $l$ hasta la $r$, dividos entre una potencia de $x$. Vamos a aprovechar esto para calcular $f(s[l,r])$ rápido.
La suma de prefijos nos ayudará a encontrar los términos deseados de forma rápida. Definamos a $p(s,i)$ como el valor hash del prefijo de tamaño $i$ de $s$. En otras palabras, $p(s,i)=f(s[1,i])=s_1+s_2x^1+s_3x^2+\dots+s_ix^{i-1}$
Utilzando $p(s,i)$ podemos obtener los términos necesarios para calcular $f(s[l,r])$. Tenemos que:
$$
\begin{align}
p(s,r)-p(s,l-1) &= (s_1+s_2x+s_3x^2+\dots+s_rx_{r-1}) - (s_1+s_2x+s_3x^2+\dots+s_{l-1}x^{l-2}) \\
&= (s_1-s_1)+(s_2x-s_2x)+\dots+(s_{l-1}x^{l-2}-s_{l-1}x^{l-2})+s_lx^{l-1}+\dots+s_rx^{r-1} \\
&= s_lx^{l-1}+s_{l+1}x^l+\dots+s_rx^{r-1}
\end{align}
$$
Estamos obteniendo los términos que necesitamos al restar $p(s,r)-p(s,l-1)$, pero con el exponente de $x$ incorrecto. El exponte del término de $s_l$ debería ser $0$, el del término de $s_{l+1}$ debería ser $1$, y así. Notemos que después de restar, el exponente del término de $s_l$ es $l-1$, por lo que si dividimos entre $x^{l-1}$, obtendremos los exponentes correctos:
$$
\begin{align}
\frac{p(s,r)-p(s,l-1)}{x^{l-1}} &= \frac{s_lx^{l-1}+s_{l+1}x^l+s_{l+2}x^{l+1}+\dots+s_rx^{r-1}}{x^{l-1}} \\
&= s_l\frac{x^{l-1}}{x^{l-1}}+s_{l+1}\frac{x^l}{x^{l-1}}+s_{l+2}\frac{x^{l+1}}{x^{l-1}}+\dots+s_r\frac{x^{r-1}}{x^{l-1}} \\
&= s_lx^0+s_{l+1}x^1+s_{l+2}x^2+\dots+s_rx^{r-l} \\
&= f(s[l,r])
\end{align}
$$
Entonces concluimos que $f(s[l,r])=\frac{p(s,r)-p(s,l-1)}{x^{l-1}}$. Si ya tenemos los valores de $p(s,i)$ para toda $i$, entonces esto se puede calcular en $O(\log(m))$, ya que necesitamos exponenciación binaria para hallar $x^{l-1}$ y su inverso multiplicativo modular. Como alternativa, podemos precalcular también los inversos de $x^i$ para toda $i$, y así calcular $f(s[l,r])$ en tiempo constante.
Sólo nos falta ver cómo precalcular $p(s,i)$. Esto es sencillo notando lo siguiente:
$$
\begin{align}
p(s,i) &= s_1+s_2x^1+s_3x^2+\dots+s_ix^{i-1} \\
&= (s_1+s_2x^1+s_3x^2+\dots+s_{i-1}x^{i-2})+s_ix^{i-1} \\
&= p(s,i-1) + s_ix^{i-1}
\end{align}
$$
Es decir, para hallar $p(s,i)$ simplemente le sumamos $s_ix^{i-1}$ a $p(s,i-1)$. Podemos guardar los valores de $p(s,i)$ en un arreglo y calcularlo desde $i=0$ hasta $i=|s|$.
#### Implementación
En un mismo problema, es posible que necesitemos encontrar el hash para más de una cadena, por lo encapsularemos la función y lo que precalculemos adentro de un `struct`:
``` C++
const int mod = 1e9 + 7; // 10^9 + 7
long long binPow (long long b, int p) {
long long res = 1;
while (p) {
if (p & 1)
(res *= b) %= mod;
(b *= b) %= mod;
p >>= 1;
}
return res;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randint (int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
int x = randint(256, mod - 1);
struct Rolling_Hash {
vector<long long> ps, inv_x;
// Recibe una cadena indexada en 0.
Rolling_Hash (string s) {
int n = s.size();
ps = inv_x = vector<long long>(n + 1);
s = " " + s;
long long inv = binPow(x, mod - 2);
long long xi = 1;
inv_x[0] = 1;
for (int i = 1; i <= n; i++) {
ps[i] = (ps[i - 1] + s[i] * xi) % mod;
inv_x[i] = inv_x[i - 1] * inv % mod;
(xi *= x) %= mod;
}
}
// Halla el valor hash de un subarreglo indexado en 1.
long long f (int l, int r) {
long long res = (ps[r] - ps[l - 1]) * inv_x[l - 1] % mod;
if (res < 0)
res += mod;
return res;
}
};
```
Un ejemplo de uso en el `main` sería el siguiente:
```C++
int main() {
string s = "abacaba";
Rolling_Hash rh(s);
cout << rh.f(2, 2) << endl;
cout << rh.f(3, 6) << endl;
cout << rh.f(5, 7) << endl;
cout << rh.f(1, 3) << endl;
cout << rh.f(1, 7) << endl;
return 0;
}
```
Contestar cada query es en tiempo $O(1)$, y precalculamos $p(s,i)$ y $x^i$ para toda $i$ en tiempo $O(|s|log(mod))$.
### Problemas
#### Algoritmo de Karp-Rabin
:::success
:information_source: **Problema**
Dadas dos cadenas $T$ y $P$, ¿cuántas veces aparece la cadena $P$ en $T$ y en qué posiciones?
**Límites:**
$1 \leq |P| \leq |T| \leq 10^6$.
**Ejemplo:**
Si $T='abcdabacabcbc'$ y $P='abc'$, entonces $P$ aparece dos veces en $T$ en las posiciones $1$ y $9$ (índexadas en $1$).
[Link.](https://acmp.ru/asp/do/index.asp?main=task&id_course=2&id_section=18&id_topic=42&id_problem=262&locale=en)
:::
Una aparición de $P$ puede ocurrir sólo en una subcadena del mismo tamaño de $P$ en $T$, por lo que podemos iterar sobre todos las subcadenas de tamaño $|P|$ de $T$ y comprobar si su valor hash es igual al de $T$.
#### Rotación cíclica
:::success
:information_source: **Problema**
La rotación ciclica de una cadena $S$ es quitar un prefijo de $S$ y pegarlo al final. Formalmente, es convertir una cadena $s_1s_2s_3s_4 \dots s_n$ en $s_{i+1}s_{i+2}\dots s_ns_1s_2\dots s_i$ para alguna $i$.
Por ejemplo, la cadena $abca$ tiene las rotaciones $abca$ (la cadena original también es rotación), $bcaa$, $caab$ y $aabc$.
Dadas dos cadenas $S$ y $T$, determinar si $S$ es rotación de $T$.
**Límites:**
$1 \leq |S| = |T| \leq 10^6$.
**Ejemplo:**
- Si $S=abca$ y $T=caab$, la respuesta es Sí.
- Si $S=abca$ y $T=acba$, la respuesta es No.
:::
Hay dos soluciones:
- Verificar si el hash de $S$ es igual a $f(T[i,n])+x^{n-i+1}f(T[1,i])$.
- Verifcar si $S$ es subtring de $T+T$, donde el operador $+$ significa concatenación.
#### Determinar si una cadena es palindromo
:::success
:information_source: **Problema**
Determinar si una cadena $S$ es palindromo. Un palindromo es una cadena que se lee igual de izquierda a derecha que de derecha a izquierda.
**Límites:**
$1 \leq |S| \leq 10^6$.
**Ejemplo:**
- Si $S=abacaba$, la respuesta es Sí.
- Si $S=abda$, la respuesta es No.
:::
Sea $S^R$ la cadena $S$ invertida ($S^R=s_ns_{n-1}\dots s_1$). La respuesta es Sí si $f(S)=f(S^R)$.
#### Determinar si una subcadena es palindromo
:::success
:information_source: **Problema**
Responde $Q$ queries. En cada query determina si la subcadena $S[l,r]$ es palindromo
**Límites:**
$1 \leq |S|,Q \leq 10^6$.
:::
Sea $S^R$ la cadena $S$ invertida ($S^R=s_ns_{n-1}\dots s_1$). La respuesta es Sí si $f(S[l,r])=f(S^R[n-r+1,n-l+1])$.
### Hash doble
#### Subcadenas distintas
:::success
:information_source: **Problema**
¿Cuántas subcadenas distintas tiene $S$?
**Límites:**
$1 \leq |S|,Q \leq 1000$.
:::
La solución es hallar el valor hash de todas las subcadenas y meterlas en un `set<int>` para contar los valores sin repetición.
En esta solución hay un detalle, y es que en todos los problemas anteriores, cada vez que comparábamos valores hash, sólo era entre parejas de cadenas, pero ahora tenemos que comparar $O(n^2)$ valores hash al mismo tiempo para comprobar cuáles son iguales entre sí. Aquí utilizamos otra técnica para analizar la probabilidad de colisión: la paradoja del cumpleaños.
Si tenemos un año de $m$ días y $n^2$ personas, entonces una [aproximación a la probabilidad de que dos personas cumplan el mismo día es](https://en.wikipedia.org/wiki/Birthday_problem#Approximations):
$$
p \approx 1-e^{\frac{\frac{n^2(n^2-1)}{2}}{m}}
$$
Haciendo una analogía con nuestro problema, hay $m=10^9+7$ valores posibles (para el primo más usado) y $n \approx 10^6$ subcadenas diferentes a las que sacar hash en el peor caso, por lo tanto la probabilidad de colisiones es:
$$
p \approx 1-e^{\frac{\frac{10^6(10^6-1)}{2}}{10^9+7}}\approx 1
$$
Es casi seguro que van a haber colisiones en el peor caso.
Una solución es usar doble hash. Vamos a elegir dos pares $(x_1,m_1)$ y $(x_2,m_2)$ de valores para $x$ y $m$, y evaluar la función hash con esos dos pares, y ahora el valor hash sería un `pair<int,int>`.
Un módulo puede ser $10^9+7$ y otro $10^9+9$, entonces los valores distintos serían apróximadamente $10^{18}$. La probabilidad de colisión ahora es:
$$
p \approx 1-e^{\frac{\frac{10^6(10^6-1)}{2}}{10^{18}}}\approx 5*10^{-7}\approx 0.000005.
$$
Que ya es una probabilidad de colisión aceptable. Si quisieramos todavía mejor probabilidad, podemos juntar más parejas $(x,m)$.
Este problema se puede resolver de forma deterministica y en mejor tiempo con [suffix array](https://cp-algorithms.com/string/suffix-array.html) o [suffix automaton](https://cp-algorithms.com/string/suffix-automaton.html).
### Más problemas:
- https://acm.timus.ru/problem.aspx?space=1&num=1517&locale=en
- https://acmp.ru/asp/do/index.asp?main=task&id_course=2&id_section=18&id_topic=43&id_problem=284&locale=en#google_vignette
- https://acmp.ru/asp/do/index.asp?main=task&id_course=2&id_section=18&id_topic=43&id_problem=285&locale=en
- https://www.hackerrank.com/contests/ab-yeh-kar-ke-dikhao/challenges/jitu-and-strings/problem
## Trie
Un trie, también conocido como árbol de prefijos, es una estructura de datos que guarda información sobre los prefijos de las cadenas de un diccionario. Esta estructura tiene las siguientes características:
- Cada nodo representa un prefijo de una o más palabras del diccionario.
- Cada arista tiene un carácter.
- Si una arista con el carácter $c$ sale del nodo que representa al prefijo $P$, entonces dicha arista apunta al nodo que representa al prefijo $Pc$.
- Si dos o más palabras tienen el mismo prefijo en común, compartirán el nodo que representa este prefijo. Esto implica que no hay nodos que representan al mismo prefijo.
- El trie es un árbol enraizado en la arista que representa al prefijo vació.
- Los datos que guardan los nodos pueden variar, pero los más comunes son:
- Un contador de las palabras que contienen el prefijo del nodo, llamado `cn`.
- Una bandera que indica si el nodo contiene una palabra completa, llamado `end`.
- La lista de adyaciencia del nodo, llamado `next`.
Se puede interpretar como un automáta finito determinista aciclo que acepta todo las palabras de un diccionario.
### Implementación
``` C++
struct Trie {
struct Node {
map<char, int> next;
int cn;
bool end;
Node () : cn(0), end(false) {}
};
// El nodo 0 es la raíz del trie.
vector<Node> vn;
Trie () : vn(1) {}
// Agrega una cadena al trie.
void insert (const string &s) {
int u = 0;
vn[0].cn++;
for (char c : s) {
if (!vn[u].next.count(c)) {
vn[u].next[c] = vn.size();
vn.pb({});
}
u = vn[u].next[c];
vn[u].cn++;
}
vn[u].end = true;
}
// Encuentra si la palabra s está en el trie
bool find (const string &s) {
int u = 0;
for (char c : s) {
if (!vn[u].next.count(c))
return false;
u = vn[u].next[c];
}
return vn[u].end;
}
};
```
Ejemplo de uso en el main:
``` C++
int main() {
Trie t;
t.insert("perro");
t.insert("perico");
t.insert("gato");
cout << t.find("gato") << endl; // 1
cout << t.find("pe") << endl; // 0
cout << t.find("leon") << endl; // 0
return 0;
}
```
Cada operación recorre todos los carácteres de una cadena, y en cada iteración accede a un map cuyo tamaño es a lo mas $|\Sigma|$. Por lo tanto la complejidad es $O(|S|\log(|\Sigma|))$.
### Problemas
#### Diccionario de palabras
:::success
:information_source: **Problema**
Tienes un diccionario de palabras originalmente vacío. Procesa $Q$ queries. Cada query es uno de dos tipos:
1. Agrega una palabra $s$ al diccionario.
2. Contesta si existe o no una palabra $t$ en el diccionario actualmente.
**Ejemplo**
| Entrada | Salida |
| - | - |
| 7 | |
| 1 gato | |
| 2 gato | Yes |
| 2 perro | No |
| 1 perro | |
| 2 perro | Yes |
| 2 pe | No |
| 2 perros | No |
:::
La solución es utilizar la misma implementación de arriba. El `main` quedaría algo así:
``` C++
int main() {
Trie t;
int Q;
cin >> Q;
while (Q--) {
int type;
string s;
cin >> type >> s;
if (type == 1) {
t.insert(s);
} else {
if (t.find(s))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
return 0;
}
```
Notar que el trie puede procesar las queries en cualquier orden, no es necesario insertar primero todas las palabras y después buscarlas.
#### Agenda telefónica
:::success
:information_source: **Problema**
Tienes una agenda telefónica originalmente vacía. Procesa $Q$ queries. Cada query es uno de dos tipos:
1. Agrega un contacto con nombre $s$ y número de telefóno $n$. Si ya existe, sobrescribelo.
2. Busca si existe el contacto con nombre $s$. Si existe, imprime su número. En caso contario imprime $-1$
**Ejemplo**
| Entrada | Salida |
| - | - |
| 7 | |
| 1 Juanito 11111111 | |
| 2 Juanito | 11111111 |
| 2 Pedrito | -1 |
| 1 Pedrito 22222222 | |
| 2 Pedrito | 22222222 |
| 1 Pedrito 33333333 | |
| 2 Pedrito | 33333333 |
:::
La búsqueda se realiza por el nombre del contacto, por lo que el diccionario sobre el que se construirá el trie son los nombres. Pero ahora los nodos deben almacenar un dato extra: los números telefónicos.
La modificación a la implementación sería algo así:
```C++
struct Trie {
struct Node {
map<char, int> next;
int cn;
bool end;
string number;
Node () : cn(0), end(false) {}
};
// El nodo 0 es la raíz del trie.
vector<Node> vn;
Trie () : vn(1) {}
// Agrega una cadena al trie.
void insert (const string &s, const string &n) {
int u = 0;
vn[0].cn++;
for (char c : s) {
if (!vn[u].next.count(c)) {
vn[u].next[c] = vn.size();
vn.pb({});
}
u = vn[u].next[c];
vn[u].cn++;
}
vn[u].end = true;
vn[u].number = n;
}
// Encuentra si la palabra s está en el trie
string find (const string &s) {
int u = 0;
for (char c : s) {
if (!vn[u].next.count(c))
return "-1";
u = vn[u].next[c];
}
if (vn[u].end)
return vn[u].number;
return "-1";
}
};
```
#### Ocurrencias de un diccionario en una cadena
:::success
:information_source: **Problema**
Tienes un diccionario con cadenas $t_1, t_2, \dots, t_m$, y una cadena $s$. Determinar cuántas ocurrencias de las palabras del diccionario existen en $s$.
:::
El trie nos permite encontrar las ocurrencias de las palabras del diccionario que empiezan en cierta posición de $s$. Si empezamos en la posición $i$ de $s$, entonces avanzamos por el trie de acuerdo a los carácateres de $s$ empezando en $i$. Repetimos este proceso para cada posición de $s$.
A continuación se presenta una modificación de la función `find` que permite hallar las ocurrencias del diccionario que empiezan en la posición $i$ de $s$:
``` C++
int find (const string &s, int i) {
int u = 0, res = 0;
while (i < (int)s.size()) {
if (!vn[u].next.count(s[i]))
break;
u = vn[u].next[s[i]];
if (vn[u].end)
res++;
i++;
}
return res;
}
```
La complejidad es $O(\sum|t_i|+|s|^2)$. Un algoritmo con mejor complejidad es el Aho-Corasick.
#### Trie sort
:::success
:information_source: **Problema**
Dadas $n$ cadenas $s_1, s_2, \dots, s_n$, ordenar las cadenas en orden lexicográfico.
Una cadena $s$ es menor lexicográficamente que $t$, si $s$ es prefijo de $t$, o si en la primera posición $i$ en la que son diferentes $s$ y $t$, se cumple que $s_i$ tiene menor valor ASCII que $t_i$.
**Ejemplo:**
Para la entrada:
abacaba
zzz
bc
aba
a
aabc
La salida debe ser:
a
aabc
aba
abacaba
bc
zzz
:::
Las cadenas ya estarían ordenadas de forma natural en el trie. La lista de adyaciencia de cada nodo mantendría ordenadas las aristas por el valor ASCII de los carácteres. Por lo que podríamos hacer un recorrido en el árbol por profundidad (DFS), recorriendo primero las aristas que tengan menor valor ASCII, y que lleguemos a un nodo donde termina una palabra, imprimimos esa palabra.
Un ejemplo de una función `dfs` que haga el recorrido es el siguiente:
```C++
void dfs (string &pre, int u) {
if (vn[u].end)
cout << pre << endl;
for (auto it = vn[u].next.begin(); it != vn[u].next.end(); it++) {
pre.pb(it->fi);
dfs(pre, it->se);
pre.pop_back();
}
}
```
Para imprimir las cadenas ordenadas, se debe llamar a la dfs desde el nodo $0$ con una cadena vacía.
La complejidad de este algoritmo de ordenamiento es $O((\sum|s_i|)\log(|\Sigma|))$.
#### Maximizar XOR
:::success
:information_source: **Problema**
Dado un arreglo de $n$ enteros $A=[a_1, a_2, \dots, a_n]$. Contestar $Q$ queries. En cada query se da un número $x$, y se desea hallar cuál es el mayor XOR posible entre $x$ y un elemento de $A$. Es decir, hallar:
$$
\max_{i=1}^n(x \oplus a_i)
$$
donde $\oplus$ es el operador XOR a nivel de bits.
**Ejemplo:**
Si tenemos $A=[6,9,2,13,5,8]$ y $x=5$, entonces los valores del XOR de $x$ con cada elemento de $A$ es:
- $a_1 \oplus x = 6 \oplus 5 = 3$
- $a_2 \oplus x = 9 \oplus 5 = 12$
- $a_3 \oplus x = 2 \oplus 5 = 7$
- $a_4 \oplus x = 13 \oplus 5 = 8$
- $a_5 \oplus x = 5 \oplus 5 = 0$
- $a_6 \oplus x = 8 \oplus 5 = 13$
El máximo XOR se obtiene con $8 \oplus 5 = 13$, entonces la respuesta es $13$.
:::
Por las propiedades de la representación binaria de un número y del XOR, podemos hacer un algoritmo greedy desde el bit más significativo hasta el bit menos significativo. En cada bit, empezando desde el más significativo, vemos si podemos hacer $1$ ese bit en la respuesta. Para eso vemos si hay elementos de $A$ que sigan activos que tenga el valor contrario que $x$ en ese bit. Si es así, nos quedamos con dichos elementos y descartamos el resto. En caso contrario, continuamos con los mismos elementos.
La respuesta tendrá prendidos los bits en las posiciones en las que pudimos elegir elementos activos que tuvieran ese bit todavía prendido.
El algoritmo greedy funciona porque nos conviene más tener el bit $i$ prendido y los bits más pequeños apagados, que tener el bit $i$ apagado y los bits más pequeños prendidos. Esto es por que $2^i > 2^{i-1}+2^{i-2}+\dots+2^0$. De hecho $2^{i-1}+2^{i-2}+\dots+2^0=2^i-1$
Este algoritmo greedy se puede simular en un trie. Guardemos la representación binaria de los elementos de $A$, con el bit más significativo en la primera posición y el menos en la última. Notar que es necesario rellenar con $0$ a la izquierda para que todas las cadenas tengan el mismo tamaño.
Una vez teniendo este trie, contestamos las queries. En cada query, recorremos el trie, intentando siempre elegir el valor contrario de cada bit. La función `query` quedaria implementada así:
```C++
// Recibe la representación binaria del número x rellenado con 0's
// a la izquierda para que tenga tamaño k.
// k es la cantidad máxima de bits que pueden tener los números.
int query (const string &s, int k) {
int u = 0, res = 0, valor_bit = 1 << (k - 1);
for (char c : s) {
if (c == '1') {
if (vn[u].next.count('0')) {
res |= valor_bit;
u = vn[u].next['0'];
} else {
u = vn[u].next['1'];
}
} else {
if (vn[u].next.count('1')) {
res |= valor_bit;
u = vn[u].next['1'];
} else {
u = vn[u].next['0'];
}
}
valor_bit >>= 1;
}
return res;
}
```
El ejmplo de arriba sería algo como:
```C++
int main() {
Trie t;
t.insert("0110"); // 6
t.insert("1001"); // 10
t.insert("0010"); // 2
t.insert("1101"); // 13
t.insert("0101"); // 5
t.insert("1000"); // 8
cout << t.query("0101", 4) << endl; // x=5. Regresa 13
return 0;
}
```
### Problemas
- https://www.spoj.com/problems/ADAINDEX/en/
- https://www.spoj.com/problems/TRYCOMP/en/
- https://atcoder.jp/contests/abc287/tasks/abc287_e
- https://judge.yosupo.jp/problem/set_xor_min
- https://oj.uz/problem/view/COCI20_vlak
- https://codeforces.com/problemset/problem/455/B
- https://www.spoj.com/problems/SUBXOR/en/
## Notas finales
### Más algoritmos de cadenas
A continuación se muestran más algoritmos y estructuras de datos de cadenas que se pueden estudiar después de los vistos en clase, ordenados por el estimado de cantidad de problemas en los que los he utilizado:
- [Algoritmo Z](https://cp-algorithms.com/string/z-function.html) y [KMP](https://cp-algorithms.com/string/prefix-function.html).
- [Suffix Array](https://cp-algorithms.com/string/suffix-array.html).
- [Manacher](https://cp-algorithms.com/string/manacher.html).
- [Aho-Corasick](https://cp-algorithms.com/string/aho_corasick.html).
- [Suffix Automaton](https://cp-algorithms.com/string/suffix-automaton.html).
- Palindromic Tree.
### Un arreglo se puede transformar en cadena
Todos los algoritmos de cadenas se pueden aplicar también a arreglos. Es como si cada elemento del arreglo fuera un carácter.
Sign in with Wallet
Connect another wallet