Алгоритмы на строках (Хеширование и строки). Поиск подстроки в строке: наивный алгоритм, алгоритм Рабина-Карпа, алгоритм Кнута-Морриса-Пратта, Z-функция. Бор

• Алгоритмы на строках
• Хеширование

Алгоритм Кнута-Морриса-Пратта (КМП-алгоритм)

Поиск подстроки в строке: даны образец для поиска $S$ и строка $T$, найти индекс, начиная с которого $S$ содержится в строке $T$. Если $S$ не содержится в $T$  - вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число).

При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.

Описание алгоритма и оценка времени работы

Рассмотрим сравнение строк на позиции $i$, где образец $S[0, m - 1]$ сопоставляется с частью текста $T[ i, i + m - 1 ]$. Предположим, что первое несовпадение произошло между $T[i + j]$ и $S[ j ]$, где $1 < j < m$. Тогда $T[ i, i + j - 1 ] = S[ 0, j - 1 ] = P$ и $a = T[ i + j ] \ne S[ j ] = b$.

При сдвиге вполне можно ожидать, что префикс (начальные символы) образца $S$ сойдется с каким-нибудь суффиксом (конечные символы) текста $P$. Длина наиболее длинного префикса, являющегося одновременно суффиксом, есть префикс-функция от строки $S$ для индекса $j$.

Это приводит нас к следующему алгоритму: пусть $\rm{\pi}[ j ]$ — префикс-функция от строки $S[ 0, m - 1 ]$ для индекса $j$. Тогда после сдвига мы можем возобновить сравнения с места $T[ i + j ]$ и $S[ \rm{\pi}[ j ] ]$ без потери возможного местонахождения образца. Можно показать, что таблица $\rm{\pi}$ может быть вычислена (амортизационно) за $\Theta( m )$ сравнений перед началом поиска. А поскольку строка $T$ будет пройдена ровно один раз, суммарное время работы алгоритма будет равно $\Theta(m + n)$, где $n$ — длина текста $T$.