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

Определение:

Префикс-функция (англ. prefix-function) от строки — массив длин наибольших бордеров для каждой позиции этой строки

Здесь и далее считаем, что символы в строках нумеруются с [math]1[/math].

Определим префикс-функцию от строки [math]s[/math] в позиции [math]i[/math] следующим образом: [math]\pi(s, i) = \max\limits_{k = 1..i - 1} \{k : [/math] [math]s[1..k] = s[i - k + 1..i] \}[/math]. Если мы не нашли такого [math]k[/math], то [math]\pi(s, i)=0[/math].

Наивный алгоритм

Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк. Обозначим длину строки за [math]n[/math].

Псевдокод

int[] prefixFunction(string s)
     fill([math]\pi[/math], 0)
     for i = 1 to n
         for k = 1 to i
             if s[1..k] == s[i - k + 1..i]
                 [math]\pi[/math][i] = k
     return [math]\pi[/math]

Пример

Рассмотрим строку [math]abcabcd[/math], для которой значение префикс-функции равно [math][0,0,0,1,2,3,0][/math].

Шаг	Строка	Значение функции
[math]1[/math]	a	0
[math]2[/math]	ab	0
[math]3[/math]	abc	0
[math]4[/math]	abca	1
[math]5[/math]	abcab	2
[math]6[/math]	abcabc	3
[math]7[/math]	abcabcd	0

Время работы

Всего [math]O(n^2)[/math] итераций цикла, на каждой из который происходит сравнение строк за [math]O(n)[/math], что дает в итоге [math]O(n^3)[/math].

Эффективный алгоритм

Вносятся несколько важных замечаний:

• Заметим, что [math]\pi[i + 1] \leqslant \pi[i] + 1[/math]. Чтобы показать это, рассмотрим суффикс,оканчивающийся на позиции [math]i + 1[/math] и имеющий длину [math]\pi[i + 1][/math], удалив из него последний символ, мы получим суффикс, оканчивающийся на позиции [math]i[/math] и имеющий длину [math]\pi[i + 1] - 1[/math], следовательно неравенство [math]\pi[i + 1] \gt \pi[i] + 1[/math] неверно.
• Избавимся от явных сравнений строк. Пусть мы вычислили [math]\pi[i][/math], тогда, если [math]s[i + 1] = s[\pi[i]][/math], то [math]\pi[i + 1] = \pi[i] + 1[/math]. Если окажется, что [math]s[i + 1] \ne s[\pi[i]][/math], то нужно попытаться попробовать подстроку меньшей длины. Хотелось бы сразу перейти к такому бордеру наибольшей длины, для этого подберем такое [math]k[/math], что [math]k = \pi(i) - 1[/math]. Делаем это следующим образом. За исходное [math]k[/math] необходимо взять [math]\pi(i - 1)[/math], что следует из первого пункта. В случае, когда символы [math]s[k+1][/math] и [math]s[i][/math] не совпадают, [math]\pi(k)[/math] — следующее потенциальное наибольшее значение [math]k[/math], что видно из рисунка. Последнее утверждение верно, пока [math]k\gt 0[/math], что позволит всегда найти его следующее значение. Если [math]k=0[/math], то [math]\pi(i)=1[/math] при [math]s[i] = s[1][/math] , иначе [math]\pi(i)=0[/math].

Псевдокод

int[] prefixFunction(string s)
     [math]\pi[/math][1] = 0
     for i = 2 to n
         k = [math]\pi[/math][i-1]
         while k > 0 and s[i] != s[k + 1] 
             k = [math]\pi[/math][k]
         if s[i] == s[k + 1]
             k++
         [math]\pi[/math][i] = k
     return [math]\pi[/math]

Время работы

Время работы алгоритма составит [math]O(n)[/math]. Для доказательства этого нужно заметить, что итоговое количество итераций цикла [math]\mathrm{while}[/math] определяет асимптотику алгоритма. Теперь стоит отметить, что [math]k[/math] увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение [math]k = n - 1[/math]. Поскольку внутри цикла [math]\mathrm{while}[/math] значение [math]k[/math] лишь уменьшается, получается, что [math]k[/math] не может суммарно уменьшиться больше, чем [math]n-1[/math] раз. Значит цикл [math]\mathrm{while}[/math] в итоге выполнится не более [math]n[/math] раз, что дает итоговую оценку времени алгоритма [math]O(n)[/math].

Построение префикс-функции по Z-функции

Постановка задачи

Дан массив с корректной [math] z-[/math] функцией для строки [math]s[/math], получить за [math]O(n)[/math] массив с префикс—функцией для строки [math]s[/math].

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

Пусть [math]Z-[/math] функция хранится в массиве [math]z[1..n],[/math] префикс-функцию будем записывать в массив [math]p[1..n][/math]. Пойдем по массиву [math]z[/math] слева направо, заметим, что если [math]z[i] \gt 0, [/math] то для всех элементов с индексом [math]i + j[/math], где [math]0 \leqslant j \lt  z[i] [/math] значение [math]p[i + j] [/math] будет не меньше, чем длина подстроки с [math] i [/math] по [math] i + j[/math], что равно [math]j + 1[/math] (видно еще из рисунка). Также заметим, что если мы уже установили значение в какое-то [math]p[k][/math] то менять уже не нужно, так как если мы установили в [math]j-[/math]ую позицию с позиции [math]k[/math], где [math]k \lt i[/math], то такое изменение только уменьшит значение [math] p[j][/math], действительно, значение после первого присвоения [math]p_{old}[i + j] = i + j - k + 1 \gt i + j - i + 1 = j + 1 = p_{new}[i + j][/math]. В итоге получаем алгоритм: идем слева направо по массиву [math]z[/math] и пусть мы сейчас находимся на позиции [math]i[/math], тогда пытаемся записать в [math]p[/math] от позиции [math]i + z[i] - 1 [/math] до [math]i[/math] значение [math] j - i + 1,[/math] где [math]j[/math] пробегает все значения [math] 0.. z[i] - 1[/math], пока не наткнемся на уже инициализированный элемент. Слева от него все значения тоже нет смысла обновлять, поэтому прерываем эту итерацию. Теперь посчитаем асимптотику алгоритма. Каждый элемент устанавливается ровно один раз. Дальше на нем может случиться только [math] break [/math]. Поэтому в итоге внутренний цикл суммарно отработает за количество установленных значений + количество [math]break[/math]. Количество значений установленных [math]— n[/math]. А число [math]break[/math] тоже будет не больше [math]n[/math], так как каждый [math]break[/math] переводит внешний цикл на следующую итерацию , то есть число операции будет не больше [math] 2 \cdot n[/math] откуда получаем асимптотику [math]O(n).[/math]

Псевдокод

int[] buildPrefixFunctionFromZFunction(int[] z)
  int[] p = new int[z.length]
  for i = 2 to z.length - 1
    for j = z[i] - 1 downto 0
      if p[i + j] > 0 
        break
      else
        p[i + j] = j + 1
  return p

Доказательство корректности

Пусть наш алгоритм неправильно посчитал какие-то значение [math]p[i][/math]. Пусть [math] ans[1..n][/math] это массив, содержащий корректную префикс-функцию. Рассмотрим позицию в которой наш алгоритм посчитал некорректно, пусть это позиция [math]i[/math]. Заметим, что [math]ans[i]\geqslant p[i][/math] так как алгоритм записывает длину подстроки, оканчивающуюся на [math]i-[/math]ом символе, соответственно правильный ответ, не может быть меньше нашего. Предположим, что [math]ans[i] \gt p[i], [/math] посмотрим на значение [math]z[i - ans[i] + 1][/math] оно больше либо равно [math]ans[i][/math]. Но тогда наш алгоритм бы записал в [math] p[i][/math] корректное значение.

Построение строки по префикс-функции

Постановка задачи

Восстановить строку по префикс-функции за [math]O(n)[/math], считая алфавит неограниченным.

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

Пусть в массиве [math]p[/math] хранятся значения префикс-функции, в [math]s[/math] будет записан ответ. Пойдем по массиву [math]p[/math] слева направо.

Пусть мы хотим узнать значение [math]s[i][/math]. Для этого посмотрим на значение [math]p[i][/math]: если [math]p[i] =0[/math] тогда в [math]s[i][/math] запишем новый символ, иначе [math]s[i] = s[p[i]][/math]. Обратим внимание, что [math]s[p[i]][/math] нам уже известно, так как [math]p[i] \lt i[/math].

Реализация

string buildFromPrefix(int[] p):
  s = "" 
  for i = 0 to p.length - 1
      if p[i] == 0     
          s += new character
      else
          s += s[p[i]]
  return s

Доказательство корректности алгоритма

Докажем, что если нам дали корректную префикс-функцию, то наш алгоритм построит строку с такой же префикс-функцией. Также заметим, что строк с такой префикс-функцией может быть много, и алгоритм строит только одну из них.

Пусть [math]p[/math] данная префикс-функция, [math]s'[/math] правильная строка, строку [math]s[/math] построил наш алгоритм, [math] q [/math] массив значений префикс-функции для [math]s[/math].

Докажем корректность индукцией по длине массива префикс-функции полученной строки. Для начала заметим, что на предыдущие значения массива [math] q [/math] прибавление нового символа не влияет, так как при подсчёте префикс-функции на [math] i [/math]-ой позиции рассматриваются символы на позициях не больше [math] i [/math]. Поэтому достаточно показать, что очередное значение префикс-функции будет вычислено правильно.

• База очевидна для строки длины [math]1[/math].
• Переход: пусть до [math]n[/math]-ой позиции мы построили строку, что [math]p[1..n - 1] = q[1..n - 1][/math]. Возможны два случая:
  • [math]p[n] = 0[/math]. Тогда мы добавляем новый символ, поэтому [math]q[n][/math] тоже будет равно [math]0[/math].
  • [math]p[n] \gt 0[/math]. По свойствам префикс-функции [math] s'[p[n]] = s'[n] [/math] — суффикс и префикс строки [math] s' [/math] длины [math] p[n] [/math] продолжаются одним символом, значит, надо на текущую позицию строки [math] s [/math] поставить символ [math] s[p[n]] [/math]. Если значение префикс-функции увеличивается, значит, текущим символом продолжается префикс длины [math] p[n - 1] [/math], а из свойств следует, что [math] p[n - 1] \geqslant p[n] - 1 [/math]. По предположению индукцию значение [math] q[n - 1] [/math] будет вычислено верно. А если значение префикс-функции не увеличивается, значит, символ [math] s[n] [/math] должен продолжить префикс меньшей длины, а в текущее значение префикс-функции запишется как раз длина нового бордера. Для этого будут использованы значения префикс-функции с меньшими индексами, которые посчитаны верно, опять же по предположению индукции.

См. также

• Z-функция
• Алгоритм Кнута-Морриса-Пратта

Источники информации

• Википедия — Префикс-функция
• MAXimal :: algo — Префикс-функция
• Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296 ISBN 978-5-8459-0857-5