Условие задачи: Дана строка s длины n. Требуется вычислить префикс-функцию — массив p длины n, где p[i] равно длине наибольшего собственного префикса подстроки s[0…i], совпадающего с её суффиксом.

Формат входных данных:
Первая строка — целое число n (1 ≤ n ≤ 1 000 000).
Вторая строка — сама строка s длины n (латиница, без пробелов).

Формат выходных данных: n чисел p[0] … p[n-1], разделённых пробелом (как правило p[0] = 0).

Решение: Поддерживаем переменную k — значение p[i-1]. Для позиции i уменьшением k ← p[k-1] «поднимаемся» по ссылкам, пока символы s[i] и s[k] не совпадут или k = 0. Если совпали, увеличиваем k++ и сохраняем p[i] = k. Алгоритм обходит строку один раз, сложность O(n), память O(n).

После цикла массив p содержит префикс-функцию.

Например,

даёт

Доказательство корректности (скетч): Инвариант: перед обработкой позиции i переменная k равна p[i-1]. Цикл while гарантирует, что после выхода k — длина наибольшего собствен­ного префикса, совпадающего с суффиксом s[0…i-1], который ещё может расшириться символом s[i]. Если расширение возможно, прибавляем 1; иначе p[i]=0. Следовательно, каждое p[i] корректно, а работа линейна, так как k только уменьшается внутри цикла.