Префикс-функция¶

Префикс-функция — это функция от строки, которая для каждой позиции строки определяет длину наибольшего собственного префикса, совпадающего с суффиксом подстроки, оканчивающейся на этой позиции. Формально, для строки \( s \) длины \( n \) префикс-функция \( \pi[i] \) (где \( i \) от 0 до \( n-1 \)) равна максимальному значению \( k < i+1 \), такому, что \( s[0..k-1] = s[i-k+1..i] \). Значение \( \pi[0] \) обычно полагается равным 0. Префикс-функция является фундаментальным инструментом в алгоритмах обработки строк, в частности, в алгоритме Кнута — Морриса — Пратта (КМП) для поиска подстроки.

¶Определение и свойства

Префикс-функция задаётся для строки \( s \) длины \( n \). Для каждого индекса \( i \) (от 0 до \( n-1 \)) вычисляется \( \pi[i] \) — длина наибольшего собственного префикса строки \( s[0..i] \), который одновременно является её суффиксом. Собственный префикс — это префикс, не равный всей строке. Таким образом, \( \pi[i] \) — это максимальное \( k < i+1 \), при котором первые \( k \) символов строки совпадают с последними \( k \) символами подстроки \( s[0..i] \).

Основные свойства:

• \( \pi[0] = 0 \) для всех строк.
• Значения \( \pi[i] \) монотонно возрастают не более чем на 1 при увеличении \( i \): \( \pi[i+1] \le \pi[i] + 1 \).
• Если \( \pi[i] = k \), то для всех меньших значений \( j < k \), таких, что \( s[0..j-1] = s[i-j+1..i] \), выполняется, что \( j \) также является длиной некоторого собственного префикса-суффикса, и эти значения можно получить, последовательно применяя префикс-функцию к предыдущим позициям.

¶Алгоритм вычисления

Классический алгоритм вычисления префикс-функции работает за линейное время \( O(n) \) и использует константную дополнительную память. Алгоритм был предложен Дональдом Кнутом, Джеймсом Моррисом и Воганом Праттом в 1970-х годах.

¶Описание алгоритма

Пусть \( s \) — строка длины \( n \). Массив \( \pi \) инициализируется нулями. Для \( i \) от 1 до \( n-1 \) выполняется:

1. Установить \( k = \pi[i-1] \).
2. Пока \( k > 0 \) и \( s[i] \neq s[k] \), установить \( k = \pi[k-1] \).
3. Если \( s[i] = s[k] \), то увеличить \( k \) на 1.
4. Присвоить \( \pi[i] = k \).

Алгоритм использует уже вычисленные значения префикс-функции для «перескока» по цепочке возможных префиксов-суффиксов, что обеспечивает линейную сложность.

¶Пример вычисления

Рассмотрим строку \( s = \) «abacaba». Вычисление по шагам:

• \( i = 0 \): \( \pi[0] = 0 \).
• \( i = 1 \): символы «a» и «b» не совпадают, \( k = 0 \), \( \pi[1] = 0 \).
• \( i = 2 \): \( k = 0 \), \( s[2] = 'a' \), \( s[0] = 'a' \) — совпадают, \( k = 1 \), \( \pi[2] = 1 \).
• \( i = 3 \): \( k = 1 \), \( s[3] = 'c' \), \( s[1] = 'b' \) — не совпадают, \( k = \pi[0] = 0 \), \( s[3] = 'c' \), \( s[0] = 'a' \) — не совпадают, \( \pi[3] = 0 \).
• \( i = 4 \): \( k = 0 \), \( s[4] = 'a' \), \( s[0] = 'a' \) — совпадают, \( k = 1 \), \( \pi[4] = 1 \).
• \( i = 5 \): \( k = 1 \), \( s[5] = 'b' \), \( s[1] = 'b' \) — совпадают, \( k = 2 \), \( \pi[5] = 2 \).
• \( i = 6 \): \( k = 2 \), \( s[6] = 'a' \), \( s[2] = 'a' \) — совпадают, \( k = 3 \), \( \pi[6] = 3 \).

Итоговая префикс-функция: \( [0, 0, 1, 0, 1, 2, 3] \).

¶Применение

¶Поиск подстроки (алгоритм Кнута — Морриса — Пратта)

Основное применение префикс-функции — реализация алгоритма КМП для поиска всех вхождений образца \( p \) в текст \( t \). Для этого строится строка \( s = p + '#' + t \), где '#' — символ, не встречающийся ни в \( p \), ни в \( t \). Вычисляется префикс-функция для \( s \). Когда значение \( \pi[i] \) становится равным длине образца \( |p| \), это означает, что образец найден в тексте, оканчиваясь на позиции \( i - |p| \) в исходной строке \( s \). Алгоритм работает за \( O(|p| + |t|) \).

¶Выделение повторяющихся подстрок

Префикс-функция позволяет находить наименьший период строки. Если \( n \) делится на \( n - \pi[n-1] \), то строка является периодической с периодом \( n - \pi[n-1] \). Например, для строки «abcabcabc» \( n = 9 \), \( \pi[8] = 6 \), \( n - \pi[8] = 3 \), строка имеет период 3.

¶Автоматы и обработка строк

Префикс-функция используется для построения конечного автомата для поиска подстроки (алгоритм Ахо — Корасик, хотя там применяется более общая концепция — функция неудач). Также она применяется в алгоритмах сжатия данных (например, в алгоритме Лемпеля — Зива — Велча, LZW) и в биоинформатике для анализа последовательностей ДНК.

¶Вариации и обобщения

¶Z-функция

Z-функция для строки \( s \) — это массив \( z[i] \), где \( z[i] \) — длина наибольшего префикса строки \( s \), совпадающего с префиксом подстроки \( s[i..n-1] \). Z-функция тесно связана с префикс-функцией: обе могут быть вычислены за линейное время и преобразованы друг в друга. Алгоритм вычисления Z-функции был предложен Гасфилдом в 1997 году.

¶Префикс-функция для нескольких строк

В задачах поиска множества образцов используется обобщение — построение префикс-функции для бора (trie) в алгоритме Ахо — Корасик. Там функция неудач (failure function) является аналогом префикс-функции, но для структуры дерева.

¶Реализация на языках программирования

Префикс-функция реализуется на большинстве языков программирования. Пример на Python:

``python def prefix_function(s): n = len(s) pi = [0] * n for i in range(1, n): k = pi[i - 1] while k > 0 and s[i] != s[k]: k = pi[k - 1] if s[i] == s[k]: k += 1 pi[i] = k return pi ``

Пример на C++:

``cpp vector<int> prefix_function(string s) { int n = s.size(); vector<int> pi(n); for (int i = 1; i < n; ++i) { int k = pi[i - 1]; while (k > 0 && s[i] != s[k]) k = pi[k - 1]; if (s[i] == s[k]) ++k; pi[i] = k; } return pi; } ``

¶История

Префикс-функция была впервые описана в 1970 году Дональдом Кнутом, Джеймсом Моррисом и Воганом Праттом в контексте алгоритма поиска подстроки. В 1977 году Роберт Бойер и Дж. Стротер Мур предложили альтернативный алгоритм, но префикс-функция остаётся ключевым элементом КМП. В СССР алгоритм КМП и префикс-функция изучались в рамках курсов алгоритмов и структур данных, в частности, в работах А. В. Ахо, Дж. Хопкрофта и Дж. Ульмана.

¶Интересные факты

• Префикс-функция может быть использована для построения всех собственных префиксов-суффиксов строки: последовательность \( \pi[n-1], \pi[\pi[n-1]-1], \pi[\pi[\pi[n-1]-1]-1], \ldots \) даёт все длины таких префиксов.
• Существует алгоритм вычисления префикс-функции за \( O(n) \) без использования дополнительной памяти, кроме массива \( \pi \).
• В некоторых задачах (например, при поиске палиндромов) используется модифицированная префикс-функция для обратной строки.

¶Критика и ограничения

Префикс-функция эффективна для однократного поиска образца в тексте, но для многократного поиска или для работы с большими объёмами данных могут быть предпочтительнее другие алгоритмы, такие как алгоритм Рабина — Карпа (с хешированием) или суффиксные деревья. Также префикс-функция не позволяет напрямую обрабатывать строки с «дырками» (wildcards) без дополнительных модификаций.

¶Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013. — 1328 с.
• Ахо А. В., Хопкрофт Дж., Ульман Дж. Д. Структуры данных и алгоритмы. — М.: Вильямс, 2001. — 384 с.
• Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — СПб.: Невский Диалект, 2003. — 656 с.
• Кнут Д. Э., Моррис Дж. Х., Пратт В. Р. Быстрый поиск подстроки в тексте // SIAM Journal on Computing. — 1977. — Т. 6, № 2. — С. 323–350.