Алгоритмы и структуры данных

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

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

Алгоритм:
1. Вычисляем хэш-функцию для искомой строки.
2. Вычисляем хэш-функцию для первой подстроки текста, длиной равной длине искомой строки.
3. Если хэш-значения совпадают, сравниваем каждый символ искомой строки с соответствующим символом подстроки текста. Если все символы совпадают, значит, мы нашли вхождение искомой строки.
4. Если хэш-значения не совпадают, перемещаем окно подстроки текста на один символ вправо и повторяем шаг 3 до конца текста.
5. Если мы достигли конца текста и не нашли вхождений искомой строки, значит, она отсутствует в тексте.

Сложность: O(n + m), где n - длина текста, а m - длина искомой строки. Однако, в худшем случае: O(n * m).

www.tgoop.com/the_algorithms/4609

6.3K viewsNov 21, 2023 at 09:02

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

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

Алгоритм:
1. Вычисляем хэш-функцию для искомой строки.
2. Вычисляем хэш-функцию для первой подстроки текста, длиной равной длине искомой строки.
3. Если хэш-значения совпадают, сравниваем каждый символ искомой строки с соответствующим символом подстроки текста. Если все символы совпадают, значит, мы нашли вхождение искомой строки.
4. Если хэш-значения не совпадают, перемещаем окно подстроки текста на один символ вправо и повторяем шаг 3 до конца текста.
5. Если мы достигли конца текста и не нашли вхождений искомой строки, значит, она отсутствует в тексте.

Сложность: O(n + m), где n - длина текста, а m - длина искомой строки. Однако, в худшем случае: O(n * m).

BY Алгоритмы и структуры данных