Что хранит префикс-функция строки и как её правильно посчитать за O(n)?
Везде в разборах КМП фигурирует «префикс-функция», но я не понимаю, что именно она хранит в каждой позиции и почему её можно посчитать за линию, а не за O(n^2). Можете дать строгое определение и каноническую реализацию на C++?
2 ответа
Префикс-функция p[i] строки s — это длина наибольшего собственного префикса подстроки s[0..i], который одновременно является её суффиксом. «Собственного» = не равного всей подстроке, иначе ответ был бы тривиально i+1. Например, для abacaba: p = [0,0,1,0,1,2,3] — на последней позиции совпали aba в начале и в конце.
Ключ к линейности: при переходе от i-1 к i ответ не может вырасти больше чем на 1. Если s[i] == s[p[i-1]], то p[i] = p[i-1] + 1. Иначе откатываемся по уже посчитанным значениям j = p[j-1], пока не найдём совпадение или не дойдём до нуля.
vector<int> prefix_function(const string& s) {
int n = s.size();
vector<int> p(n, 0);
for (int i = 1; i < n; ++i) {
int j = p[i - 1];
while (j > 0 && s[i] != s[j]) j = p[j - 1];
if (s[i] == s[j]) ++j;
p[i] = j;
}
return p;
}
Амортизированная сложность — O(n) по времени, O(n) по памяти. Доказательство: значение j увеличивается максимум на 1 за итерацию внешнего цикла (всего +n за всё время), а каждый шаг while уменьшает j хотя бы на 1, значит суммарно while не сделает больше n шагов.
Добавлю частую ошибку новичков: путают «собственный префикс» с любым. Если по ошибке разрешить весь префикс, получите p[i] = i+1 для константной строки вроде aaaa вместо [0,1,2,3], и весь КМП сломается. Условие j > 0 в while и старт с i = 1 (а не 0) тут принципиальны — p[0] всегда 0.