String Matching

Solución - Algoritmo de Knuth-Morris-Pratt

Definimos un arreglo $\pi_S$ sobre un string $S$ tal que $\pi_S[i]$ guarda la longitud del prefijo no trivial más largo del string entero que es equivalente a un sufijo que termina en la posición $i$ . Formalmente,

\pi_S[i] = \max\{k \: | \: 1 \leq k < i \text{ and } S[0:k - 1] \equiv S[i - (k - 1): i]\}

Si buscamos el string $P$ dentro del string $T$ , creamos un string nuevo $S = P + \# + T$ , donde $\#$ es cualquier carácter arbitrario que no aparece en ninguno de los dos strings. Luego construimos un arreglo $\pi_S$ con el algoritmo KMP . La respuesta es simplemente la cantidad de índices dentro de $\pi_S$ que son iguales a $|P|$ (la longitud de $P$ ).

C++Python

Complejidad temporal: $\mathcal{O}(n + m)$


#include <bits/stdc++.h>
using namespace std;
 
namespace str {
/** Computes the Pi array of s. */
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;
}
}  // namespace str
 
int main() {
	string P, T;
	cin >> T >> P;
	string S = P + '#' + T;
	vector<int> pi = str::pi(S);
	int ans = 0;
	for (int l : pi) {
		if (l == P.size()) { ans++; }
	}
	cout << ans << '\n';
}


from typing import List
 
 
def pi(s: str) -> List[int]:
	"""Computes the Pi array of s."""
	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
 
 
T = input()
P = input()
S = P + "#" + T
pi = pi(S)
ans = 0
for l in pi:
	if l == len(P):
		ans += 1
 
print(ans)

Solución - Algoritmo Z

Como en la solución anterior, ahora definimos un arreglo $z_S$ tal que $z_S[i]$ es la longitud del prefijo más largo que empieza en el índice $i$ y es equivalente a un prefijo del string entero. Formalmente,

z_S[i] = \max\{k \: | \: 1 \leq k\text{ and } S[0:k - 1] \equiv S[i:i+k-1]\}

Como antes, para el patrón $P$ y el texto $T$ , creamos un string nuevo $S = P + '\#' + T$ y construimos el arreglo $z_S$ con el algoritmo Z . La respuesta es la cantidad de índices dentro de $z_S$ que son iguales a $|P|$ .

C++

Complejidad temporal: $\mathcal{O}(n + m)$


#include <bits/stdc++.h>
using namespace std;
 
namespace str {
// Computes the Z-array of s
vector<int> z(const string &s) {
	int n = (int)s.size();
	vector<int> z_S(n);
	for (int i = 1, l = 0, r = 0; i < n; i++) {
		if (i <= r) { z_S[i] = min(z_S[i - l], r - i + 1); }
		while (i + z_S[i] < n && s[z_S[i]] == s[i + z_S[i]]) { z_S[i]++; }
		if (i + z_S[i] - 1 > r) {
			l = i;
			r = i + z_S[i] - 1;
		}
	}
	return z_S;
}
}  // namespace str
 
int main() {
	string P, T;
	cin >> T >> P;
	string S = P + '#' + T;
	vector<int> z = str::z(S);
	int ans = 0;
	for (int l : z) {
		if (l == P.size()) { ans++; }
	}
	cout << ans << '\n';
}

Solución - Algoritmo de Rabin-Karp

Precomputamos el hash rolling de $P$ y de $T$ . Cada subcadena de longitud $|P|$ se puede comparar por igualdad en tiempo $\mathcal{O}(1)$ . Como hay relativamente pocas comparaciones, basta un solo conjunto de valores de hash (aunque no viene mal añadir más). Usar base de hash $9973$ y módulo $10^9 + 7$ alcanza (ver el módulo de hashing de strings para más detalles sobre esta elección).

C++

Complejidad temporal: $\mathcal{O}(n + m)$


#include <bits/stdc++.h>
using namespace std;
 
namespace str {
// Computes the rolling hash of s with power P and modulo M
vector<long long> rhash(const string &s, const long long P, const long long M) {
	int n = (int)s.size();
	vector<long long> rhash_S(n);
	for (int i = 0; i < n; i++) {
		if (i != 0) { rhash_S[i] = rhash_S[i - 1] * P % M; }
		rhash_S[i] = (rhash_S[i] + (long long)s[i]) % M;
	}
	return rhash_S;
}
}  // namespace str
 
const long long hashPow = 9973, hashMod = 1e9 + 7;
 
int main() {
	string P, T;
	cin >> T >> P;
	vector<int> Phash = str::rhash(P, hashPow, hashMod),
	            Thash = str::rhash(T, hashPow, hashMod);
 
	long long ppow = 1;  // hashPow to the power of |P| modulo hashMod
	for (int i = 0; i < P.size(); i++) { ppow = (ppow * hashPow) % hashMod; }
 
	int ans = 0;
	for (int i = 0; i + P.size() - 1 < T.size(); i++) {
		long long r = Thash[i + P.size() - 1];
		long long l = i == 0 ? 0 : (Thash[i - 1] * ppow % hashMod);
		long long curHash = (r - l + hashMod) % hashMod;
		if (curHash == Phash.back()) { ans++; }
	}
	cout << ans << '\n';
}