Префикс-функция — различия между версиями
Строка 15: | Строка 15: | ||
} | } | ||
*'''Время работы''' | *'''Время работы''' | ||
− | + | Сперва отметим очевидный из определения факт: <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
Определение
Префикс-функцией цепочки
называется функцияАлгоритм вычисления
- Псевдокод
k <- 0(0) <- 0 for (i <- 1..n - 1) { while (k > 0 && s[i] s[k]) k <- (k - 1) if (s[i] = s[k]) k <- k + 1 (i) <- k }
- Время работы
Сперва отметим очевидный из определения факт:
для любого . В самом деле, в противном случае не максимально. Теперь рассмотрим произвольную итерацию внешнего цикла . Возможно одно из трёх:- . Тогда значение увеличивается на 1, цикл не итерируется
- . Тогда значение не изменяется, цикл не итерируется
- итерируется хотя бы раз. При каждой итерации значение может, очевидно, лишь уменьшаться, при этом, в силу отмеченного выше очевидного наблюдения, общее число итераций для всех итераций не превышает
Таким образом, общее время работы -
.