← Static tasks

E101. Алгоритм Рабина-Карпа поиска подстроки в строке за O (N)

emaxx algorithm

#algorithm#emaxx#hashing#search#string

Task

Источник: e-maxx.ru/algo, страница PDF 301.

Этот алгоритм базируется на хэшировании строк, и тех, кто не знаком с темой, отсылаю к "Алгоритмам хэширования в задачах на строки".

Авторы алгоритма - Рабин (Rabin) и Карп (Karp), 1987 год. Дана строка S и текст T, состоящие из маленьких латинских букв. Требуется найти все вхождения строки S в текст T за время O (|S| + |T|). Алгоритм. Посчитаем хэш для строки S. Посчитаем значения хэшей для всех префиксов строки T. Теперь переберём все подстроки T длины |S| и каждую сравним с |S| за время O (1).

Реализация

string s, t; // входные данные

// считаем все степени p

const int p = 31;

vector<long long> p_pow (max (s.length(), t.length()));

p_pow[0] = 1;

for (size_t i=1; i<p_pow.size(); ++i)

p_pow[i] = p_pow[i-1] * p;

// считаем хэши от всех префиксов строки T

vector<long long> h (t.length());

for (size_t i=0; i<t.length(); ++i)

{

h[i] = (t[i] - 'a' + 1) * p_pow[i];

if (i)  h[i] += h[i-1];

}

// считаем хэш от строки S

long long h_s = 0;

for (size_t i=0; i<s.length(); ++i)

h_s += (s[i] - 'a' + 1) * p_pow[i];

// перебираем все подстроки T длины |S| и сравниваем их

for (size_t i = 0; i + s.length() - 1 < t.length(); ++i)

{

long long cur_h = h[i+s.length()-1];

if (i)  cur_h -= h[i-1];

// приводим хэши к одной степени и сравниваем

if (cur_h == h_s * p_pow[i])

cout << i << ' ';

}

C# solution

auto-draft, review before submit
using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    string s, t; // входные данные
    // считаем все степени p
    const int p = 31;
    vector<long> p_pow (max (s.length(), t.length()));
    p_pow[0] = 1;
    for (size_t i=1; i<p_pow.size(); ++i)
            p_pow[i] = p_pow[i-1] * p;
    // считаем хэши от всех префиксов строки T
    vector<long> h (t.length());
    for (size_t i=0; i<t.length(); ++i)
    {
            h[i] = (t[i] - 'a' + 1) * p_pow[i];
            if (i)  h[i] += h[i-1];
    }
    // считаем хэш от строки S
    long h_s = 0;
    for (size_t i=0; i<s.length(); ++i)
            h_s += (s[i] - 'a' + 1) * p_pow[i];
    // перебираем все подстроки T длины |S| и сравниваем их
    for (size_t i = 0; i + s.length() - 1 < t.length(); ++i)
    {
            long cur_h = h[i+s.length()-1];
            if (i)  cur_h -= h[i-1];
            // приводим хэши к одной степени и сравниваем
            if (cur_h == h_s * p_pow[i])
                    Console.WriteLine( i << ' ';
    }
}

C++ solution

matched/original
string s, t; // входные данные
// считаем все степени p
const int p = 31;
vector<long long> p_pow (max (s.length(), t.length()));
p_pow[0] = 1;
for (size_t i=1; i<p_pow.size(); ++i)
        p_pow[i] = p_pow[i-1] * p;
// считаем хэши от всех префиксов строки T
vector<long long> h (t.length());
for (size_t i=0; i<t.length(); ++i)
{
        h[i] = (t[i] - 'a' + 1) * p_pow[i];
        if (i)  h[i] += h[i-1];
}
// считаем хэш от строки S
long long h_s = 0;
for (size_t i=0; i<s.length(); ++i)
        h_s += (s[i] - 'a' + 1) * p_pow[i];
// перебираем все подстроки T длины |S| и сравниваем их
for (size_t i = 0; i + s.length() - 1 < t.length(); ++i)
{
        long long cur_h = h[i+s.length()-1];
        if (i)  cur_h -= h[i-1];
        // приводим хэши к одной степени и сравниваем
        if (cur_h == h_s * p_pow[i])
                cout << i << ' ';
}

Java solution

auto-draft, review before submit
import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    string s, t; // входные данные
    // считаем все степени p
    const int p = 31;
    vector<long> p_pow (max (s.length(), t.length()));
    p_pow[0] = 1;
    for (size_t i=1; i<p_pow.size(); ++i)
            p_pow[i] = p_pow[i-1] * p;
    // считаем хэши от всех префиксов строки T
    vector<long> h (t.length());
    for (size_t i=0; i<t.length(); ++i)
    {
            h[i] = (t[i] - 'a' + 1) * p_pow[i];
            if (i)  h[i] += h[i-1];
    }
    // считаем хэш от строки S
    long h_s = 0;
    for (size_t i=0; i<s.length(); ++i)
            h_s += (s[i] - 'a' + 1) * p_pow[i];
    // перебираем все подстроки T длины |S| и сравниваем их
    for (size_t i = 0; i + s.length() - 1 < t.length(); ++i)
    {
            long cur_h = h[i+s.length()-1];
            if (i)  cur_h -= h[i-1];
            // приводим хэши к одной степени и сравниваем
            if (cur_h == h_s * p_pow[i])
                    System.out.println( i << ' ';
    }
}

Explanation

Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.