Использование Рабина-Карпа для поиска нескольких паттернов в строке

Question

Согласно записи в википедии об алгоритме сопоставления строк Рабина-Карпа, его можно использовать для одновременного поиска нескольких различных шаблонов в строке, сохраняя при этом линейную сложность. Ясно, что это легко сделать, когда все шаблоны имеют одинаковую длину, но я все еще не понимаю, как мы можем сохранить сложность O (n) при одновременном поиске шаблонов с различной длиной. Может кто-нибудь, пожалуйста, пролить свет на это?

Изменить (декабрь 2011 г.):

С тех пор статья в Википедии была обновлена ​​и больше не претендует на совпадение с несколькими шаблонами разной длины в O (n).

Answer 1

Я не уверен, что это правильный ответ, но в любом случае:

При построении значения хеша мы можем проверить соответствие в наборе хеш-строк. Ака, значение current hash. Хеш-функция / код обычно реализуется в виде цикла, и внутри этого цикла мы можем вставить наш быстрый поиск.

Конечно, мы должны выбрать m, чтобы получить максимальную длину строки из набора строк.

Обновление: Из Википедии,

[...]
for i from 1 to n-m+1
         if hs ∈ hsubs
             if s[i..i+m-1] = a substring with hash hs
                 return i
         hs := hash(s[i+1..i+m]) // <---- calculating current hash
[...]

Мы вычисляем текущий хэш с шагом m. На каждом шаге есть временное значение хеша, которое мы можем посмотреть (O (1) сложность) в наборе хешей. Все хеши будут иметь одинаковый размер, то есть 32 бит.

Обновление 2: амортизированная (средняя) O (n) сложность времени?

Выше я сказал, что m должен иметь максимальную длину строки. Оказывается, мы можем использовать противоположное.
С хэшированием для поиска смещения подстроки и фиксированным размером m мы можем достичь сложности O (n).

Если у нас есть строки переменной длины, мы можем установить m на минимальную длину строки. Кроме того, в наборе хэшей мы связываем хэш не со всей строкой, а с ее первыми m-символами.
Теперь при поиске текста мы проверяем, есть ли текущий хеш в наборе хешей, и проверяем соответствующие строки на совпадение.

Этот метод увеличит количество ложных срабатываний, но в среднем он имеет O (n) временную сложность.

Answer 2

Это потому, что значения хешей подстрок связаны математически. Вычисление хеша H (S, j) (хеш символов, начиная с j-й позиции строки S ) занимает O (м) времени на строка длиной м . Но как только вы это сделаете, вычисление H (S, j + 1) может быть выполнено в постоянное время, потому что H (S, j + 1) может быть выражено как функция H (S, j) .

O (м) + O (1) => O (м) , то есть линейное время.

Вот ссылка , где это описано более подробно (см., Например, раздел «Что делает Рабин-Карп быстрым?»)