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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Оптимизация)
(Оптимизация)
Строка 39: Строка 39:
 
*<tex>\pi(i + 1)</tex> превосходит <tex>pi(i)</tex> не больше чем на <tex>1</tex>. Действительно, если <tex>\pi(i+1) > \pi(i) + 1</tex>, тогда <tex>\pi(i+1) - 1 > \pi(i)</tex>, получили противоречие.
 
*<tex>\pi(i + 1)</tex> превосходит <tex>pi(i)</tex> не больше чем на <tex>1</tex>. Действительно, если <tex>\pi(i+1) > \pi(i) + 1</tex>, тогда <tex>\pi(i+1) - 1 > \pi(i)</tex>, получили противоречие.
 
*Избавимся от явных сравнений строк. Пусть мы вычислили <tex>\pi(i)</tex> и <tex>s[\pi(i) + 1] = s[i + 1]</tex>, тогда очевидно <tex>\pi(i+1) = \pi(i) + 1</tex>. Если же условие <tex>s[\pi(i) + 1] = s[i + 1]</tex> ложно, то хотелось бы найти наибольшую длину <tex> j</tex>, для которой верно <tex>\pi(i+1) = j + 1</tex>. Когда мы найдем такое <tex>j</tex> нам достаточно будет сравнить <tex>s[j + 1]</tex> и <tex>s[i + 1]</tex>, при их равенстве <tex>\pi(i+1) = j + 1</tex> будет верно. Будем искать наше <tex>j</tex> пока оно больше нуля, при равенстве нулю <tex>\pi(i+1) = 1</tex>, если <tex>s[i] = s[1]</tex>, иначе нулю. Общая схема алгоритма у нас есть, теперь нужно только научиться искать <tex>j</tex>.
 
*Избавимся от явных сравнений строк. Пусть мы вычислили <tex>\pi(i)</tex> и <tex>s[\pi(i) + 1] = s[i + 1]</tex>, тогда очевидно <tex>\pi(i+1) = \pi(i) + 1</tex>. Если же условие <tex>s[\pi(i) + 1] = s[i + 1]</tex> ложно, то хотелось бы найти наибольшую длину <tex> j</tex>, для которой верно <tex>\pi(i+1) = j + 1</tex>. Когда мы найдем такое <tex>j</tex> нам достаточно будет сравнить <tex>s[j + 1]</tex> и <tex>s[i + 1]</tex>, при их равенстве <tex>\pi(i+1) = j + 1</tex> будет верно. Будем искать наше <tex>j</tex> пока оно больше нуля, при равенстве нулю <tex>\pi(i+1) = 1</tex>, если <tex>s[i] = s[1]</tex>, иначе нулю. Общая схема алгоритма у нас есть, теперь нужно только научиться искать <tex>j</tex>.
*Для поиска <tex>j</tex> нам стоит использовать равенство <tex>j = \pi(j)</tex>, когда <tex>s[j+1] = s[i+1]</tex> ложно, взяв за исходное <tex> j = \pi(i)</tex>, это позволит выбирать <tex>j</tex> по убыванию вплоть до нуля, так как очевидно, что <tex>\pi(x) \geq \pi(\pi(x))</tex>.
+
*Для поиска <tex>j</tex> нам стоит использовать равенство <tex>j = \pi(j)</tex>, когда <tex>s[j+1] = s[i+1]</tex> ложно, взяв за исходное <tex> j = \pi(i)</tex>, это позволит выбирать <tex>j</tex> по убыванию вплоть до нуля, так как очевидно, что <tex>\pi(x) \geq \pi(\pi(x))</tex> для любых <tex>x</tex>.
 
===Псевдокод===
 
===Псевдокод===
 
   '''Prefix_function''' (<tex>s</tex>)
 
   '''Prefix_function''' (<tex>s</tex>)

Версия 14:36, 4 апреля 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])
      pi = 0
      for i = 1 to n
          for j = 1 to i - 1
               if s[1..j] == s[i - j + 1..i]
                    pi[i] = j
      return pi

Время работы

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

Оптимизация

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

  • [math]\pi(i + 1)[/math] превосходит [math]pi(i)[/math] не больше чем на [math]1[/math]. Действительно, если [math]\pi(i+1) \gt \pi(i) + 1[/math], тогда [math]\pi(i+1) - 1 \gt \pi(i)[/math], получили противоречие.
  • Избавимся от явных сравнений строк. Пусть мы вычислили [math]\pi(i)[/math] и [math]s[\pi(i) + 1] = s[i + 1][/math], тогда очевидно [math]\pi(i+1) = \pi(i) + 1[/math]. Если же условие [math]s[\pi(i) + 1] = s[i + 1][/math] ложно, то хотелось бы найти наибольшую длину [math] j[/math], для которой верно [math]\pi(i+1) = j + 1[/math]. Когда мы найдем такое [math]j[/math] нам достаточно будет сравнить [math]s[j + 1][/math] и [math]s[i + 1][/math], при их равенстве [math]\pi(i+1) = j + 1[/math] будет верно. Будем искать наше [math]j[/math] пока оно больше нуля, при равенстве нулю [math]\pi(i+1) = 1[/math], если [math]s[i] = s[1][/math], иначе нулю. Общая схема алгоритма у нас есть, теперь нужно только научиться искать [math]j[/math].
  • Для поиска [math]j[/math] нам стоит использовать равенство [math]j = \pi(j)[/math], когда [math]s[j+1] = s[i+1][/math] ложно, взяв за исходное [math] j = \pi(i)[/math], это позволит выбирать [math]j[/math] по убыванию вплоть до нуля, так как очевидно, что [math]\pi(x) \geq \pi(\pi(x))[/math] для любых [math]x[/math].

Псевдокод

 Prefix_function ([math]s[/math])
      pi = 0
      for i = 2 to n
          j = pi[i - 1] 
          while j > 0 && s[i] != s[j + 1]
              j = pi[j]
          if s[i] == s[j + 1]
              j++
          pi[i] = j
      return pi

Время работы

В итоге мы получили алгоритм выполняющий [math]O(n)[/math] итераций за [math]O(1)[/math], что дает нам итоговое [math]O(n)[/math].

Литература

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