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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
(Алгоритм)
Строка 4: Строка 4:
 
Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк.
 
Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк.
 
===Пример===
 
===Пример===
Рассмотрим строку abcabcd, для которой префикс-функции равно <tex>[0,0,0,1,2,3,0]</tex>.
+
Рассмотрим строку abcabcd, для которой значение префикс-функции равно <tex>[0,0,0,1,2,3,0]</tex>.
 
{| class="wikitable"
 
{| class="wikitable"
 
! Шаг || Строка || Значение функции
 
! Шаг || Строка || Значение функции
Строка 22: Строка 22:
 
| <tex>7</tex> || abcabcd || 0
 
| <tex>7</tex> || abcabcd || 0
 
|}
 
|}
 +
 
==Псевдокод==
 
==Псевдокод==
 
   '''Prefix_function''' (<tex>s</tex>)
 
   '''Prefix_function''' (<tex>s</tex>)

Версия 23:03, 24 марта 2012

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

Псевдокод

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

Время работы

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