E110. Поиск подстроки в строке с помощью Z- или Префикс-функции
Источник: 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# решение
auto-draft, проверить перед отправкой// C# draft for: Поиск подстроки в строке с помощью Z- или Префикс-функции
// Original e-maxx article has no compact code listing in the extracted PDF text.C++ решение
сопоставлено/оригинал// C++ source for: Поиск подстроки в строке с помощью Z- или Префикс-функции
// Compact code block was not extracted from this article.Java решение
auto-draft, проверить перед отправкой// Java draft for: Поиск подстроки в строке с помощью Z- или Префикс-функции
// Original e-maxx article has no compact code listing in the extracted PDF text.Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.