Использование Rabin-Karp для поиска нескольких шаблонов в строке
-
19-09-2019 - |
Вопрос
В соответствии с запись в Википедии в алгоритме сопоставления строк Рабина-Карпа его можно использовать для поиска нескольких различных шаблонов в строке одновременно, сохраняя при этом линейную сложность.Понятно, что это легко сделать, когда все шаблоны имеют одинаковую длину, но я все еще не понимаю, как мы можем сохранить сложность O (n) при одновременном поиске шаблонов разной длины.Может кто-нибудь, пожалуйста, пролить немного света на это?
Редактировать (декабрь 2011):
С тех пор статья в Википедии была обновлена и больше не претендует на соответствие нескольким шаблонам разной длины в O (n).
Решение
Я не уверен, что это правильный ответ, но в любом случае:
При построении значение хэша мы можем проверить на совпадение в наборе строковых хэшей.Иначе говоря, тот текущий хэш-значение.Хэш-функция / код обычно реализуется в виде цикла, и внутри этого цикла мы можем вставить наш быстрый просмотр.
Конечно, мы должны выбрать 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) временную сложность.
Другие советы
Это потому, что хэш-значения подстрок связаны математически.Вычисление хэша H(S, j) (хэш символов , начинающихся с j - й позиции строки S) принимает O(м) время в строке длиной m.Но как только у вас это будет, вычисляя H(S, j+1) может быть выполнено в постоянное время, потому что H(S, j+1) может быть выражена как функция от H(S, j).
O (m) + O(1) => O(m), т. е.линейное время.
Вот ссылка где это описано более подробно (см., например,раздел "Что делает Рабина-Карпа быстрым?")