Значение слова префикс-функция

Пре́фикс-фу́нкция от строки (обозначается π(S, i); где S ∈ Σ - строка; 2 ≤ i ≤ ∣S∣ - длина префикса в S) — длина наибольшего префикса строки S[1…i], (исключая вырожденный случай, где префикс совпадает с этой строкой, т.е. π(S, i) = ∣S∣), который одновременно является её суффиксом .

Т.е. в строке S и её префиксе длиной i нужно найти такой префикс максимальной длины, который был бы суффиксом данной строки.

Часто префикс-функцию записывают в виде вектора длиной ∣S∣ − 1. Например, для строки "abcdabscabcdabia" префикс-функция будет такой: . Иногда для полноты считают, что π(S, 1) = 0.

Эта функция используется, например, в алгоритме Кнута — Морриса — Пратта .1