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

2012-06-12T09:43:53Z

91.122.0.36: /* Время работы */

Префикс-функция строки <tex>s</tex> {{---}} функция <tex>\pi(i) = max \{ k | k < i,</tex> <tex>s[1..k] = s[i - k + 1..i] \}</tex>.

==Алгоритм==
Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк.

===Псевдокод===
'''Prefix_function''' (<tex>s</tex>)
<tex>\pi</tex>[1..n] = 0
'''for''' i = 1 '''to''' n
'''for''' k = 1 '''to''' i - 1
'''if''' s[1..k] == s[i - k + 1..i]
<tex>\pi</tex>[i] = k
'''return''' <tex>\pi</tex>

===Пример===
Рассмотрим строку abcabcd, для которой значение префикс-функции равно <tex>[0,0,0,1,2,3,0]</tex>.
{| class="wikitable"
! Шаг || Строка || Значение функции
|-
| <tex>1</tex> || a || 0
|-
| <tex>2</tex> || ab || 0
|-
| <tex>3</tex> || abc || 0
|-
| <tex>4</tex> || abca || 1
|-
| <tex>5</tex> || abcab || 2
|-
| <tex>6</tex> || abcabc || 3
|-
| <tex>7</tex> || abcabcd || 0
|}

===Время работы===
Всего <tex>O(n^2)</tex> итераций цикла, на каждой из который происходит сравнение строк за <tex>O(n)</tex>, что дает в итоге <tex>O(n^3)</tex>.

==Оптимизация==
Вносятся несколько важных замечаний:
*Следует заметить, что <tex>\pi(i) \le \pi(i-1) + 1</tex>. Действительно, если <tex>\pi(i) > \pi(i-1) + 1</tex>, тогда <tex>\pi(i) - 1 > \pi(i-1)</tex>, значит в <tex>\pi(i-1)</tex> не максимально возможное значение, получено противоречие.
*Нужно избавиться от явных сравнений строк. Пусть вычислено <tex>\pi(i-1)</tex> и <tex>s[\pi(i-1) + 1] = s[i]</tex>, тогда <tex>\pi(i) = \pi(i-1) + 1</tex>. Если <tex>s[\pi(i) + 1] </tex> отличается от <tex>s[i + 1]</tex>, то нужно найти наибольшую длину <tex> k</tex>, для которой верно <tex>\pi(i) = k + 1</tex>. Когда найдется такое <tex>k</tex> достаточно будет сравнить <tex>s[k + 1]</tex> и <tex>s[i]</tex>, при их равенстве <tex>\pi(i) = k + 1</tex> будет верно. Итеративно продолжается поиск <tex>k</tex>, пока оно больше нуля. Если <tex>k=0</tex>, то при <tex>s[i] = s[1]</tex> значение <tex>\pi(i)=1</tex> , иначе нулю. Общая схема алгоритма есть, теперь нужно научиться искать <tex>k</tex>.
*За исходное <tex>k</tex> нужно взять <tex>\pi(i - 1)</tex>, что следует из первого пункта. Как видно из рисунка, приведенного ниже, при совпадении символов <tex>s[k + 1]</tex> и <tex>s[i]</tex> длина наибольшего общего префикса увеличивается на единицу. В случае, когда символы <tex>s[k+1]</tex> и <tex>s[i]</tex> не совпадают, <tex>\pi(k)</tex> {{---}} следующая по максимальности длина потенциального наибольшего общего префикса, что тоже понятно из рисунка. Последнее утверждение верно, пока <tex>k>0</tex>, что позволит всегда найти его следующее значение.

[[Файл:Prefix2.jpg‎]]
===Псевдокод===
'''Prefix_function''' (<tex>s</tex>)
<tex>\pi</tex>[1] = 0
k = 0
'''for''' i = 2 '''to''' n
'''while''' k > 0 && s[i] != s[k + 1]
k = <tex>\pi</tex>[k]
'''if''' s[i] == s[k + 1]
k++
<tex>\pi</tex>[i] = k
'''return''' <tex>\pi</tex>

===Время работы===
Время работы алгоритма составит <tex>O(n)</tex>. Для доказательства этого потребуется новое обозначение <tex>w_i</tex> {{---}} количество итераций цикла <tex>while</tex> на <tex>i</tex>-ом шаге. Итоговое время работы алгоритма составит <tex>\sum\limits_{i=2}^n w_i</tex>. Теперь стоит отметить, что <tex>k</tex> увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение <tex>k = n - 1.</tex> Внутри цикла <tex>while</tex> значение <tex>k</tex> лишь уменьшается, а из предыдущего утверждения получается, что оно не может уменьшиться больше, чем <tex>n-1</tex> раз, значит <tex>\sum\limits_{i=2}^n w_i \le n</tex>, что дает итоговую оценку времени алгоритма <tex>O(n)</tex>.

== Литература ==
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296.

Викиконспекты - Вклад участника [ru]

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