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

Question

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

Редактировать (декабрь 2011):

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

Answer 1

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

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

Конечно, мы должны выбрать 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(м) время в строке длиной m.Но как только у вас это будет, вычисляя H(S, j+1) может быть выполнено в постоянное время, потому что H(S, j+1) может быть выражена как функция от H(S, j).

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

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