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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 18: Строка 18:
 
Теперь рассмотрим произвольную итерацию внешнего цикла <tex>for</tex>. Возможно одно из трёх:
 
Теперь рассмотрим произвольную итерацию внешнего цикла <tex>for</tex>. Возможно одно из трёх:
 
# <tex>s[i] = s[k]</tex>. Тогда значение <tex>k</tex> увеличивается на 1, цикл <tex>while</tex> не итерируется
 
# <tex>s[i] = s[k]</tex>. Тогда значение <tex>k</tex> увеличивается на 1, цикл <tex>while</tex> не итерируется
# <tex>k = 0 \& s[i] \ne s[k]</tex>. Тогда значение <tex>k</tex> не изменяется, цикл <tex>while</tex> не итерируется
+
# <tex>k = 0</tex> <tex>\&</tex> <tex>s[i] \ne s[k]</tex>. Тогда значение <tex>k</tex> не изменяется, цикл <tex>while</tex> не итерируется
 
# <tex>while</tex> итерируется хотя бы раз. При каждой итерации <tex>while</tex> значение <tex>k</tex> может, очевидно, лишь уменьшаться, при этом, в силу отмеченного выше очевидного наблюдения, общее число итераций <tex>while</tex> для всех итераций <tex>for</tex> не превышает <tex>n</tex>
 
# <tex>while</tex> итерируется хотя бы раз. При каждой итерации <tex>while</tex> значение <tex>k</tex> может, очевидно, лишь уменьшаться, при этом, в силу отмеченного выше очевидного наблюдения, общее число итераций <tex>while</tex> для всех итераций <tex>for</tex> не превышает <tex>n</tex>
 
Таким образом, общее время работы - <tex>O(n)</tex>.
 
Таким образом, общее время работы - <tex>O(n)</tex>.

Версия 03:35, 21 июня 2011

Определение

Префикс-функцией цепочки [math]S[/math] называется функция [math]\pi(k) = max \{ j | j \leq k \& s[0..j - 1] = s[k - j + 1..k] \}[/math]

Алгоритм вычисления

[math] n = |S|[/math]

  • Псевдокод
 k <- 0
 [math]\pi[/math](0) <- 0
 for (i <- 1 .. (n - 1)) {
   while (k > 0 && s[i] [math]\ne[/math] s[k])
     k <- [math]\pi[/math](k - 1)
   if (s[i] = s[k])
     k <- k + 1
   [math]\pi[/math](i) <- k
 }
  • Время работы

Сперва отметим очевидный из определения факт: [math]\pi(k + 1) - \pi(k) \leq 1[/math] для любого [math]k[/math]. В самом деле, в противном случае [math]\pi(k)[/math] не максимально. Теперь рассмотрим произвольную итерацию внешнего цикла [math]for[/math]. Возможно одно из трёх:

  1. [math]s[i] = s[k][/math]. Тогда значение [math]k[/math] увеличивается на 1, цикл [math]while[/math] не итерируется
  2. [math]k = 0[/math] [math]\&[/math] [math]s[i] \ne s[k][/math]. Тогда значение [math]k[/math] не изменяется, цикл [math]while[/math] не итерируется
  3. [math]while[/math] итерируется хотя бы раз. При каждой итерации [math]while[/math] значение [math]k[/math] может, очевидно, лишь уменьшаться, при этом, в силу отмеченного выше очевидного наблюдения, общее число итераций [math]while[/math] для всех итераций [math]for[/math] не превышает [math]n[/math]

Таким образом, общее время работы - [math]O(n)[/math].