Алгоритм Рабина-Карпа - Каков наихудший случай O (m * n) для данного входа?

algorithm rabin-karp

1024 просмотра

2 ответа

В коде кода верхнего кодера РК:

// correctly calculates a mod b even if a < 0
function int_mod(int a, int b)
{
  return (a % b + b) % b;
}

function Rabin_Karp(text[], pattern[])
{
  // let n be the size of the text, m the size of the
  // pattern, B - the base of the numeral system,
  // and M - a big enough prime number

  if(n < m) return; // no match is possible

  // calculate the hash value of the pattern
  hp = 0;
  for(i = 0; i < m; i++) 
    hp = int_mod(hp * B + pattern[i], M);

  // calculate the hash value of the first segment 
  // of the text of length m
  ht = 0;
  for(i = 0; i < m; i++) 
    ht = int_mod(ht * B + text[i], M);

  if(ht == hp) check character by character if the first
               segment of the text matches the pattern;

  // start the "rolling hash" - for every next character in
  // the text calculate the hash value of the new segment
  // of length m; E = (Bm-1) modulo M            
  for(i = m; i < n; i++) {
    ht = int_mod(ht - int_mod(text[i - m] * E, M), M);
    ht = int_mod(ht * B, M);
    ht = int_mod(ht + text[i], M);

    if(ht == hp) check character by character if the
                 current segment of the text matches
                 the pattern; 
  }
}

Написано что

К сожалению, все еще есть случаи, когда нам придется запускать весь внутренний цикл «наивного» метода для каждой начальной позиции в тексте - например, при поиске шаблона «aaa» в строке «aaaaaaaaaaaaaaaaaaaaaaaaa» - так в в худшем случае нам все еще понадобится (n * m) итераций.

Но не остановится ли алгоритм на самой первой итерации - когда он увидит, что первые три алфавита - это «а», которое соответствует стрелке?

Автор: silent_dev Источник Размещён: 08.11.2019 11:24

Ответы (2)


1 плюс

Предположим, что искомая строка - это не «aaa», а какая-то другая строка, хэш которой совпадает с хешем «aaa». Тогда сравнение будет необходимо в каждой точке.

Конечно, мы ожидаем, что сравнение завершится неудачей раньше, чем mсимволы, но это может потребовать символов o (m).

Сказав это, обычное использование RK состоит в том, чтобы найти все (перекрывающиеся) экземпляры, и в этом случае приведенный пример будет явно o (mn).

Автор: rici Размещён: 20.08.2016 03:03

1 плюс

Алгоритм Рабина-Карпа сохраняет хеш-значения всех подстрок textразмера Mи сопоставляет их со значением хеш-значения pattern. Теперь может быть несколько подстрок с одинаковым значением хеш-функции.

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

В случае pattern = "AAA"и text = "AAAAAAAAAAAAA"есть O(n)подстроки, соответствующие значению хеша pattern. И для каждого совпадения нам нужно повторять, чтобы подтвердить O(m)время; отсюда сложность наихудшего случая O(n*m).

Автор: Shashwat Размещён: 26.03.2018 04:44
Вопросы из категории :
32x32