Как построить КМП-автомат (таблицу переходов) из префикс-функции и зачем он нужен?
Обычный КМП при несовпадении откатывается по префикс-функции в цикле while. Слышал, что можно заранее построить «автомат» — таблицу aut[состояние][символ], и тогда обработка идёт без откатов, по одному переходу на символ. Зачем это нужно и как построить таблицу?
2 ответа
КМП-автомат — это детерминированный автомат, где состояние = длина уже совпавшего префикса шаблона (0..m), а aut[state][c] сразу даёт новое состояние при чтении символа c, без всякого while. Это полезно, когда шаблон один, а текстов/переходов много (например, ДП по строкам: «сколько строк длины L не содержат шаблон» — там нужно ходить по состояниям автомата в матрице/ДП).
Строится из префикс-функции. Для состояния state и символа c: если state < m и c == pat[state], переход в state+1. Иначе берём готовый переход из состояния pref[state-1] (рекуррентно уже посчитанного).
vector<array<int,26>> build_automaton(const string& pat) {
int m = pat.size();
vector<int> pref = prefix_function(pat);
vector<array<int,26>> aut(m + 1);
for (int state = 0; state <= m; ++state)
for (int c = 0; c < 26; ++c) {
if (state < m && c == pat[state] - 'a')
aut[state][c] = state + 1;
else
aut[state][c] = (state == 0) ? 0 : aut[pref[state - 1]][c];
}
return aut;
}
Построение — O(m · Σ) (Σ = размер алфавита), обработка текста потом — O(n) ровно, без амортизации и откатов. Состояние m означает найденное вхождение.
Где это реально выручает: ДП с запретом подстроки. Состояние ДП = (длина обработанного текста, состояние КМП-автомата), переход — aut[state][c]; если попали в состояние m, эта ветка содержит шаблон и её отбрасывают. Без автомата (с while-откатами) такой ДП написать чисто нельзя — нужна именно явная функция переходов. Для одного поиска подстроки автомат избыточен (память O(m·Σ)), его строят ради комбинаторики на автомате.