Algoritmo de Rabin-Karp para matching de strings

Este algoritmo se basa en el concepto de hashing, así que si no se está familiarizado con el hashing de strings, consultar el artículo de hashing de strings.

Este algoritmo fue publicado por Rabin y Karp en 1987.

Problema: Dados dos strings — un patrón $s$ y un texto $t$ —, determinar si el patrón aparece en el texto y, si aparece, enumerar todas sus ocurrencias en tiempo $O(|s| + |t|)$ .

Algoritmo: Calcular el hash del patrón $s$ . Calcular los valores de hash de todos los prefijos del texto $t$ . Ahora, podemos comparar una subcadena de longitud $|s|$ con $s$ en tiempo constante usando los hashes calculados. Así, comparamos cada subcadena de longitud $|s|$ con el patrón. Esto tomará un tiempo total de $O(|t|)$ . Por lo tanto, la complejidad final del algoritmo es $O(|t| + |s|)$ : se requiere $O(|s|)$ para calcular el hash del patrón y $O(|t|)$ para comparar cada subcadena de longitud $|s|$ con el patrón.

Implementación


vector<int> rabin_karp(string const& s, string const& t) {
    const int p = 31; 
    const int m = 1e9 + 9;
    int S = s.size(), T = t.size();

    vector<long long> p_pow(max(S, T)); 
    p_pow[0] = 1; 
    for (int i = 1; i < (int)p_pow.size(); i++) 
        p_pow[i] = (p_pow[i-1] * p) % m;

    vector<long long> h(T + 1, 0); 
    for (int i = 0; i < T; i++)
        h[i+1] = (h[i] + (t[i] - 'a' + 1) * p_pow[i]) % m; 
    long long h_s = 0; 
    for (int i = 0; i < S; i++) 
        h_s = (h_s + (s[i] - 'a' + 1) * p_pow[i]) % m; 

    vector<int> occurrences;
    for (int i = 0; i + S - 1 < T; i++) {
        long long cur_h = (h[i+S] + m - h[i]) % m;
        if (cur_h == h_s * p_pow[i] % m)
            occurrences.push_back(i);
    }
    return occurrences;
}

Algoritmo de Rabin-Karp para matching de strings

Implementación

Problemas de práctica