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

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

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

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

Ответы

Ответ 1

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

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

Конечно, мы должны выбрать 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).

Ответ 2

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

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

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