Префикс-функция — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
(Оптимизация)
Строка 38: Строка 38:
 
==Оптимизация==
 
==Оптимизация==
 
Внесем несколько важных замечаний:
 
Внесем несколько важных замечаний:
*Заметим, что <tex>\pi(i)</tex> превосходит <tex>\pi(i-1)</tex> не больше, чем на <tex>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) \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>s[i] = s[1]</tex> {{---}} <tex>\pi(i)=1</tex> , иначе нулю. Общая схема алгоритма у нас есть, теперь нужно только научиться искать <tex>k</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>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</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</tex>.

Версия 14:02, 10 июня 2012

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

Алгоритм

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

Псевдокод

Prefix_function ([math]s[/math])
     [math]\pi[/math][1..n] = 0
     for i = 1 to n
         for k = 1 to i - 1
             if s[1..k] == s[i - k + 1..i]
                 [math]\pi[/math][i] = k
     return [math]\pi[/math]

Пример

Рассмотрим строку abcabcd, для которой значение префикс-функции равно [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) \le \pi(i-1) + 1[/math]. Действительно, если [math]\pi(i) \gt \pi(i-1) + 1[/math], тогда [math]\pi(i) - 1 \gt \pi(i-1)[/math], значит в [math]\pi(i-1)[/math] не максимально возможное значение, получили противоречие.
  • Избавимся от явных сравнений строк. Пусть мы вычислили [math]\pi(i-1)[/math] и [math]s[\pi(i-1) + 1] = s[i][/math], тогда [math]\pi(i) = \pi(i-1) + 1[/math]. Если [math]s[\pi(i) + 1] [/math] отличается от [math]s[i + 1][/math], то нужно найти наибольшую длину [math] k[/math], для которой верно [math]\pi(i) = k + 1[/math]. Когда мы найдем такое [math]k[/math] нам достаточно будет сравнить [math]s[k + 1][/math] и [math]s[i][/math], при их равенстве [math]\pi(i) = k + 1[/math] будет верно. Итеративно ищем [math]k[/math] пока оно больше нуля. Если оно равно нулю, то при [math]s[i] = s[1][/math][math]\pi(i)=1[/math] , иначе нулю. Общая схема алгоритма у нас есть, теперь нужно только научиться искать [math]k[/math].
  • За исходное [math]k[/math] нужно взять [math]\pi(i - 1)[/math], что следует из первого пункта. Как видно из рисунка, приведенного ниже, при совпадении символов [math]s[k + 1][/math] и [math]s[i][/math] длина наибольшего общего префикса увеличивается на единицу. В случае, когда символы [math]s[k+1][/math] и [math]s[i][/math] не совпадают, [math]\pi(k)[/math] — следующая по максимальности длина потенциального наибольшего общего префикса, что тоже понятно из рисунка. Последнее утверждение продолжается по индукции, и получается требуемый поиск [math]k[/math].

Prefix2.jpg

Псевдокод

Prefix_function ([math]s[/math])
     [math]\pi[/math][1] = 0
     for i = 2 to n
         k = [math]\pi[/math][i - 1] 
         while k > 0 && 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]k[/math] связывается с текущим ее значением в алгоритме. Начальное значение этого потенциала равно нулю. На каждой итерации цикла [math]while[/math] значение [math]k[/math] уменьшается, поскольку [math]\pi(k) \lt k[/math]. Поскольку [math]\pi(k) \ge 0[/math] значение этой переменной не бывает отрицательным. Также значение [math]k[/math] изменяется не более чем на 1 внутри тела цикла [math]for[/math]. Поскольку перед входом в цикл выполняется [math] k \lt i[/math] и поскольку значение переменной [math]i[/math] увеличивается в каждой итерации цикла [math]for[/math], справедливость неравенства [math]k \lt i[/math] сохраняется (подтверждая тот факт, что соблюдается также неравенство [math]\pi(i) \lt i [/math]). Каждое выполнение тела цикла [math]while[/math] можно оплатить соответствующим уменьшение потенциальной функции, поскольку [math]\pi(k) \lt k [/math]. Кроме этого значение потенциальной функции возрастает не более чем на 1, из-за этого амортизированная стоимость тела цикла [math]for[/math][math]O(1)[/math]. Так как всего [math]n[/math] итераций, и поскольку конечное значение потенциальной функции по величине не меньше, чем ее начальное значение, полное время работы в наихудшем случае равно [math]O(n)[/math].

Литература

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