Автомат префикс-функции

Заранее посчитать, куда ведёт каждый символ из каждого состояния. Тогда шаг по тексту стоит константу, а откаты становятся не нужны.

3 мин

У префикс-функции есть неприятная особенность: шаг необратим. Мы умеем дописать символ, но не умеем откатить последний, а потом дописать другой — придётся пересчитывать.

Задача, где это мешает: текст набирается по одному символу, надо после каждого символа знать число вхождений шаблона, и иногда приходит запрос «сотри последние $k$ символов».

Наивно: хранить все значения $\pi$ и при откате обрезать массив. Корректно, но амортизация ломается — оценка «сумма подъёмов не меньше суммы спусков» опиралась на то, что мы не откатываемся. Специально подобранным чередованием «допиши — сотри» легко получить квадрат.

Состояния и переходы

Заведём вершину на каждую длину префикса шаблона: $0, 1, \ldots, m$ . Текущая вершина — текущее значение префикс-функции склейки.

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

Тогда шаг по тексту — одно обращение в таблицу. Откат — возврат в запомненное состояние. И то, и другое за $O(1)$ .

Как посчитать переходы

Пусть go[v][c] — куда ведёт символ c из вершины v.

Если c совпадает с очередным символом шаблона, то есть c == t[v], ответ очевиден: v + 1.

Иначе надо откатиться по бордеру и попробовать снова — то есть сделать ровно то, что делает while в префикс-функции. Но это уже посчитано: откат ведёт в вершину pi[v-1], а для неё все переходы известны, если считать вершины по возрастанию.

vector<array<int, ALPHA>> buildAutomaton(const string& t) {
    int m = t.size();
    vector<int> pi = prefixFunction(t);
    vector<array<int, ALPHA>> go(m + 1);
    for (int v = 0; v <= m; v++)
        for (int c = 0; c < ALPHA; c++) {
            if (v < m && t[v] == 'a' + c) go[v][c] = v + 1;
            else go[v][c] = (v == 0) ? 0 : go[pi[v - 1]][c];
        }
    return go;
}

Три строки по существу. Вся хитрость — в том, что вторая ветка не считает ничего заново, а копирует готовую строку таблицы.

Построение — $O(m \cdot |\Sigma|)$ , память столько же. Для латиницы и шаблона в $10^5$ символов это 2,6 миллиона int, около 10 МБ: помещается, но об этом стоит помнить.

Проверено: на 20 000 пар «шаблон, текст» состояния автомата после каждого символа совпали со значениями префикс-функции склейки.

Почему `v == 0` разбирается отдельно

Из нулевой вершины откатываться некуда: бордера у пустого префикса нет. Если символ не подошёл, остаёмся в нуле. Без этой проверки pi[v-1] обратится к pi[-1].

Последняя вершина

Вершина $m$ — «шаблон найден целиком». Очередного символа шаблона у неё нет, поэтому первая ветка не срабатывает никогда, и все её переходы копируются из go[pi[m-1]].

Это же и есть автоматическая замена ручного len = pi[len - 1] после найденного вхождения.

Где ещё пригодится

Автомат превращает поиск в динамику по состояниям. Типичная постановка: сколько существует строк длины $L$ над данным алфавитом, не содержащих шаблон? Заводим $dp[i][v]$ — число строк длины $i$ , приводящих в состояние $v$ ; переходы берём из таблицы, состояние $m$ запрещаем.

Без автомата такую динамику не написать: переход «дописать символ» должен стоить константу.