108
правок
Изменения
Новая страница: «==Определение== Префикс-функцией строки <tex>S</tex> называется функция <tex>\pi(k) = max \{ j | j < k \& s[0..j] …»
==Определение==
Префикс-функцией строки <tex>S</tex> называется функция <tex>\pi(k) = max \{ j | j < k \& s[0..j] = s[k - j..k] \}</tex>
==Алгоритм вычисления==
<tex> n = |S|</tex>
*'''Псевдокод'''
k <- 0
<tex>\pi</tex>(0) <- 0
for (i <- 1..n - 1) {
while (k > 0 && s[i] != s[k])
k <- <tex>\pi</tex>(k - 1)
if (s[i] = s[k])
k <- k + 1
<tex>\pi</tex>(i) <- k
}
*'''Время работы'''
Для начала отметим очевидный из определения факт: <tex>\pi(k + 1) - \pi(k) \leq 1</tex> для любого <tex>k</tex>. В самом деле, в противном случае <tex>\pi(k)</tex> не максимально.
Теперь рассмотрим произвольную итерацию внешнего цикла <tex>for</tex>. Возможно одно из трёх:
# <tex>s[i] = s[k]</tex>. Тогда значение <tex>k</tex> увеличивается на 1, цикл <tex>while</tex> не итерируется
# <tex>k = 0 \& s[i] != 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>|S|</tex>
Таким образом, общее время работы - <tex>O(|S|)</tex>.
Префикс-функцией строки <tex>S</tex> называется функция <tex>\pi(k) = max \{ j | j < k \& s[0..j] = s[k - j..k] \}</tex>
==Алгоритм вычисления==
<tex> n = |S|</tex>
*'''Псевдокод'''
k <- 0
<tex>\pi</tex>(0) <- 0
for (i <- 1..n - 1) {
while (k > 0 && s[i] != s[k])
k <- <tex>\pi</tex>(k - 1)
if (s[i] = s[k])
k <- k + 1
<tex>\pi</tex>(i) <- k
}
*'''Время работы'''
Для начала отметим очевидный из определения факт: <tex>\pi(k + 1) - \pi(k) \leq 1</tex> для любого <tex>k</tex>. В самом деле, в противном случае <tex>\pi(k)</tex> не максимально.
Теперь рассмотрим произвольную итерацию внешнего цикла <tex>for</tex>. Возможно одно из трёх:
# <tex>s[i] = s[k]</tex>. Тогда значение <tex>k</tex> увеличивается на 1, цикл <tex>while</tex> не итерируется
# <tex>k = 0 \& s[i] != 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>|S|</tex>
Таким образом, общее время работы - <tex>O(|S|)</tex>.
