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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 15: Строка 15:
 
   }
 
   }
 
*'''Время работы'''
 
*'''Время работы'''
Для начала отметим очевидный из определения факт: <tex>\pi(k + 1) - \pi(k) \leq 1</tex> для любого <tex>k</tex>. В самом деле, в противном случае <tex>\pi(k)</tex> не максимально.
+
Сперва отметим очевидный из определения факт: <tex>\pi(k + 1) - \pi(k) \leq 1</tex> для любого <tex>k</tex>. В самом деле, в противном случае <tex>\pi(k)</tex> не максимально.
 
Теперь рассмотрим произвольную итерацию внешнего цикла <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> не итерируется

Версия 05:14, 8 мая 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 \& 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].