Поиск подстроки в строке

Материал из Algocode wiki
Перейти к: навигация, поиск

Поиск строки в строке

Рассмотрим задачу, которая возникает каждый раз, когда вы делаете ctrl+f:

Есть большой текст \(t\). Нужно найти все вхождения строки $s$ в него.

Наивное решение со сравнением всех подстрок $t$ длины $|s|$ со строкой $s$ работает за $O(|t| \cdot |s|)$. Если текст большой, то длинные слова в нем искать становится очень долго.

Однако существует множество способов решить эту задачу за $O(|s| + |t|)$, два самых распространённых и простых из них: через префикс-функцию и через z-функцию (примечание: не «зи», а «зет»).

Как решать задачу?

Соединим подстроки $s$ и $t$ каким-нибудь символом, который не встречается ни там, ни там — обозначим пусть этот символ #. Посмотрим на [Префикс-функция|префикс-функцию]] получившейся строки $s\#t$.

string s = "choose";
string t =
    "choose life. choose a job. choose a career. choose a family. choose a fu...";

cout << s + "#" + t << endl;
cout << slow_prefix_function(s + "#" + t) << endl;
choose#choose life. choose a job. choose a career. choose a family. choose a fu...
0000000123456000000012345600000000123456000100000001234560000000000012345600000000

Видно, что все места, где значения равны 6 (длине $s$) — это концы вхождений $s$ в текст $t$.

Такой алгоритм (посчитать префикс-функцию от $s\#t$ и посмотреть, в каких позициях она равна $|s|$) называется алгоритмом Кнута-Морриса-Пратта.

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