Описание тега rabin-karp

Описание тега Вопросы с тегом
Алгоритм сопоставления строк Рабина-Карпа - это алгоритм сопоставления строк, который использует скользящую хеш-функцию для ускорения поиска.

Вики

В информатике Rabin–Karp algorithm это строка алгоритма поиска. Для текста длинойn а также p выкройки комбинированной длины m, его среднее время работы в лучшем случае равно O(n+m) в космосе O(p), но его худшее время O(nm).

Псевдокод алгоритма

function RabinKarp(string s[1..n], string sub[1..m])
  hsub := hash(sub[1..m]);  hs := hash(s[1..m])        
  for i from 1 to n-m+1
    if hs = hsub
      if s[i..i+m-1] = sub
        return i
    hs := hash(s[i+1..i+m])
  return not found

Использование тегов

Тег rabin-karp может использоваться для задач, связанных с программированием, при реализацииRabin-Karp algorithm на любом языке программирования. Избегайте теоретических и концептуальных вопросов о Stackru, используя тег rabin-karp.

Подробнее