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

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

Версия 16:30, 12 июня 2012

Префикс-функция строки [math]s[/math] — функция [math]\pi(i) = max \{ k | k \lt i,[/math] [math]s[1..k] = s[i - k + 1..i] \}[/math], где [math]k[/math] принадлежит расширенному множеству натуральных чисел.

Алгоритм

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

Псевдокод

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

Prefix2.jpg

Псевдокод

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

Литература

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