E110. Поиск подстроки в строке с помощью Z- или Префикс-функции

emaxx algorithm

#algorithm#emaxx#kmp#search#string

Task

Источник: e-maxx.ru/algo, страница PDF 348.

Даны строки S и T. Требуется найти все вхождения строки S в текст T за O (N), где N - суммарная длина строк S и T.

Алгоритм

Образуем строку S$T, где $ - некий разделитель, который не встречается ни в S, ни в T. Вычислим для полученной строки префикс-функцию P за O (N). Пройдёмся по массиву P, и рассмотрим все его элементы, которые равны |S| (длине S). По определению префикс-фунции, это означает, что в это месте оканчивается подстрока, совпадающая с |S|, т.е. искомое вхождение. Таким образом, мы нашли все вхождения. Этот алгоритм называется алгоритмом КМП (Кнута-Морриса-Пратта). Теперь решим эту же задачу с помощью Z-функции. Построим за O (N) массив Z - Z-функцию строки S$T. Пройдёмся по всем его элементам, и рассмотрим те из них, которые равны |S|. По определению, в этом месте начинается подстрока, совпадающая с S. Таким образом, мы нашли все вхождения.

C# solution

auto-draft, review before submit

// C# draft for: Поиск подстроки в строке с помощью Z- или Префикс-функции
// Original e-maxx article has no compact code listing in the extracted PDF text.

C++ solution

matched/original

// C++ source for: Поиск подстроки в строке с помощью Z- или Префикс-функции
// Compact code block was not extracted from this article.

Java solution

auto-draft, review before submit

// Java draft for: Поиск подстроки в строке с помощью Z- или Префикс-функции
// Original e-maxx article has no compact code listing in the extracted PDF text.

Explanation

Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.