Префикс-функция
Версия от 03:22, 21 июня 2011; 192.168.0.2 (обсуждение)
Определение
Префикс-функцией цепочки
называется функцияАлгоритм вычисления
- Псевдокод
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, цикл не итерируется
- . Тогда значение не изменяется, цикл не итерируется
- итерируется хотя бы раз. При каждой итерации значение может, очевидно, лишь уменьшаться, при этом, в силу отмеченного выше очевидного наблюдения, общее число итераций для всех итераций не превышает
Таким образом, общее время работы -
.