418
правок
Изменения
Нет описания правки
==Алгоритм==
Отметим, что нумерация символов строк и элементов массива у нас начинается с <tex>0</tex>.
Сначала построим массивы: Kmp, Kmin, Rmin, Shift.
{{Определение
|definition=Обозначим за <tex>\mathrm{Kmin}(i)=i - \mathrm{Kmp}(i)</tex> функцию, возвращающую количество прыжков для позиций <tex>i</tex>, которые являются полными.
}}
{{Определение
|definition=Обозначим за <tex>\mathrm{Rmin}(i)</tex> функцию, возвращающую наименьший из периодов шаблона, которые больше позиции <tex>i</tex>, для позиций, которые являются пустыми.
}}
{{Определение
|definition=Функция сдвига <tex>\mathrm{Shift}(i) = \begin{cases}
\mathrm{Rmin}(i), & \mbox{if } \mathrm{Kmp}(i) = -1\\
\mathrm{Kmin}(i), & \mbox{otherwise}
\end{cases}</tex>
}}
==Псевдокод==
==Асимптотики==
