Поиск подстроки в строке
Поиск строки в строке
Рассмотрим задачу, которая возникает каждый раз, когда вы делаете 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-функцию, только мы будем находить не концы вхождений, а начала.