Изменения

Перейти к: навигация, поиск

Префикс-функция

7 байт убрано, 05:14, 8 мая 2011
Нет описания правки
}
*'''Время работы'''
Для начала Сперва отметим очевидный из определения факт: <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> не итерируется
Логунов Глеб
108
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/8482»

Навигация