Как искать все вхождения подстроки за O(n+m) через КМП, не склеивая строки?
Я знаю трюк «склеить pattern + '#' + text и посчитать префикс-функцию». Но на больших текстах меня смущает, что я строю массив длины n+m+1. Можно ли искать подстроку, держа в памяти только префикс-функцию шаблона (длины m), и как тогда выглядит цикл?
2 ответа
Да, классический КМП хранит только pref шаблона длины m и идёт по тексту одним проходом, не копируя его. Идея та же, что при подсчёте префикс-функции: поддерживаем j — длину уже совпавшего префикса шаблона; при несовпадении откатываемся по pref.
vector<int> kmp_search(const string& text, const string& pat) {
int n = text.size(), m = pat.size();
vector<int> pref = prefix_function(pat);
vector<int> occ;
int j = 0;
for (int i = 0; i < n; ++i) {
while (j > 0 && text[i] != pat[j]) j = pref[j - 1];
if (text[i] == pat[j]) ++j;
if (j == m) { // нашли вхождение
occ.push_back(i - m + 1);
j = pref[j - 1]; // продолжаем искать пересекающиеся
}
}
return occ;
}
Время — O(n + m), память — O(m) (только массив префикс-функции шаблона). Текст вообще не копируется. Строка j = pref[j - 1] после находки нужна, чтобы ловить перекрывающиеся вхождения (например aa в aaaa встречается 3 раза).
Маленькое предостережение про разделитель в варианте со склейкой: символ # должен НЕ встречаться ни в шаблоне, ни в тексте, иначе префикс-функция может «перепрыгнуть» границу и дать ложное вхождение длиннее m. В отдельной реализации поиска, как выше, этой проблемы нет вообще — ещё один плюс не клеить строки.