Алгоритм Кнута — Морриса — Пратта
Материал из Википедии — свободной энциклопедии
Алгоритм Кнута — Морриса — Пратта — алгоритм поиска образца в строке.
[править] Реализация
Пусть ищется строка S1 в S2. Берётся строка S=S1$S2, где символ $ — символ, не встречающийся ни в S1, ни в S2. Теперь вычисляются значения префикс-функции от строки S и всех её префиксов. Теперь, если префикс-функция от префикса S длины i равно n, где n — длина S1, и i>n, то в строке S2 есть вхождение S1, начиная с места i-2n.
