Algorithms SkillFactory

Appearance

Алгоритм Карпа-Рабина. ​

Определение ​

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

Принцип работы ​

  1. Хеширование подстроки и искомой подстроки:

    • Вычисляется хеш-значение искомой подстроки (шаблона).
    • Хеш-значение каждой подстроки строки также вычисляется с использованием хеш-функции.

  2. Сравнение хеш-значений:

    • Если хеш-значения совпадают, производится дополнительная проверка символов для подтверждения совпадения.
    • Если хеш-значения не совпадают, подстрока отбрасывается как несовпадающая.

  3. Слайдинг окно:

    • При каждой итерации окно сдвигается на один символ вправо (или влево), и вычисляется хеш-значение новой подстроки.
    • Если хеш-значения совпадают, выполняется дополнительная проверка символов.

  4. Дополнительная проверка символов:

    • Если хеш-значения совпадают, но символы подстроки и шаблона не совпадают, считается, что нет совпадения.
    • Если все символы совпадают, считается, что найдено совпадение.

Пример ​

Допустим, у нас есть строка ABCDE и мы ищем подстроку CD.

  1. Шаг 1: Преобразуем буквы в числа (например, A = 1, B = 2 и так далее).
  2. Шаг 2: Считаем хэш для CD и для каждого кусочка в строке:
  • Хэш для CD = (C = 3) + (D = 4) = 3 + 4 = 7
  • Хэш для AB = 1 + 2 = 3 (не совпадает)
  • Хэш для BC = 2 + 3 = 5 (не совпадает)
  • Хэш для CD = 3 + 4 = 7 (совпадает!)
  1. Шаг 3: Проверяем совпадение: Сравниваем подстроку CD и кусочек строки CD — они совпадают! Таким образом, мы нашли нужную подстроку в строке.