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

Задача: найти все вхождения строки $t$ в строку $s$.

Наивно — сравнивать $t$ с каждой позицией: $O(|s| \cdot |t|)$. При $|s| = |t| = 10^5$ это $10^{10}$ операций.

Сведение к префикс-функции

Склеим шаблон, разделитель и текст:

$$t \; \# \; s$$

Разделитель # обязан не встречаться ни в $t$, ни в $s$. Тогда никакой бордер склейки не может быть длиннее $|t|$: он бы содержал разделитель, а тот в строке ровно один.

Значит, $\pi[i] = |t|$ ровно в тех позициях, где закончилось вхождение шаблона.

vector<int> findAll(const string& t, const string& s) {
    string all = t + '\x01' + s;              // разделителя нет в алфавите задачи
    vector<int> pi = prefixFunction(all);
    vector<int> res;
    for (size_t i = t.size() + 1; i < all.size(); i++)
        if (pi[i] == (int)t.size())
            res.push_back(i - 2 * t.size());   // начало вхождения в s
    return res;
}

$O(|s| + |t|)$ по времени и по памяти. Проверено: на 40 000 пар строк совпало с прямым сравнением на каждой позиции.

Про разделитель

Забыть его — классическая ошибка. Без разделителя на строке t = "aa", s = "aaa" префикс-функция склейки aaaaa даёт значения $0,1,2,3,4$, и значение 2 встречается там, где вхождения нет.

Если алфавит задачи — строчные латинские буквы, годится любой символ вне их: #, $, \x01. Если во входе может быть что угодно, разделитель приходится добывать иначе — например, работать не с символами, а с числами и взять $-1$.

Когда текст не влезает в память

Текст читается по одному символу из потока, целиком его хранить нельзя. Хеши тут неудобны: для них нужен весь массив префиксных хешей.

А префикс-функция — удобна. Посмотрите на её код: обращение идёт только к pi[i-1] и к pi[len-1], где len не превосходит $|t|$. То есть весь хвост массива, относящийся к тексту, не нужен — достаточно:

• значений $\pi$ для первых $|t|$ позиций (это часть про шаблон, она не меняется);
• одного последнего значения.

vector<int> pi = prefixFunction(t);            // считаем только для шаблона
int len = 0, count = 0;
char c;
while (cin >> c) {                             // текст приходит по одному символу
    while (len > 0 && c != t[len]) len = pi[len - 1];
    if (c == t[len]) len++;
    if (len == (int)t.size()) { count++; len = pi[len - 1]; }
}

Память $O(|t|)$ вместо $O(|s| + |t|)$. При тексте в 50 миллионов символов это разница между «решено» и «превышен предел памяти».

Обратите внимание на len = pi[len - 1] после найденного вхождения: без этого мы бы застряли на состоянии len == |t|, а нам нужно продолжить поиск со следующей позиции.

Как это называется

Алгоритм известен как Кнута — Морриса — Пратта (КМП). Классическое изложение вводит его отдельно, с двумя указателями по тексту и шаблону; изложение через префикс-функцию склейки короче и не требует нового кода.

Родственные постановки

Циклический сдвиг. Является ли $b$ циклическим сдвигом $a$? Ищем $a$ в строке $b + b$. Если $|a| = |b|$ и вхождение нашлось — да.

Наибольший префикс $t$, являющийся суффиксом $s$. Это последнее значение $\pi$ у склейки, без всяких доработок.

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