418
правок
Изменения
м
Нет описания правки
{{Определение
|definition=
Обозначим за <tex>\mathrm{K_{min}}(i) = \min\{k : \ x[0 \dots i-1-k]=x[d \dots i-1]\ and\ x[i-k] \neq x[i]\}</tex>. Функция <tex>\mathrm{K_{min}}</tex> определена для всех позиций <tex>i</tex>, у которых <tex>Kmp(i) \neq -1</tex>.
}}
Если <tex>\mathrm{KminK_{min}}(i) \neq 0</tex>, то периодичность шаблона <tex>x</tex> заканчивается в позиции <tex>i</tex>.
Очевидно, что для <tex>0 < i < m</tex> позиция <tex>i</tex>:
* насыщенная, если <tex>\mathrm{KminK_{min}}(i-1) \neq 0</tex>
* ненасыщенная, иначе
{{Определение
|definition=
Обозначим за <tex>\mathrm{RminR_{min}}(i)</tex> наименьший период <tex>r</tex> шаблона <tex>x</tex> большего, чем <tex>i</tex>. Функция <tex>\mathrm{R_{min}}</tex> определена для всех позиций <tex>i</tex>, у которых <tex>Kmp(i) = -1</tex>.
}}
{{Определение
|definition=
Обозначим за <tex>\mathrm{Firstfirst}(u)</tex> наименьший число <tex>v</tex> такое, что <tex>u \leqslant h[v]</tex>.
}}
Рассмотрим случай, когда <tex>x[h[k]]=y[j+h[k]]</tex> для <tex>0 \leqslant k < r < nd</tex> и <tex>x[h[r]] \neq y[j+h[r]]</tex>.
Пусть <tex>j' = j + \mathrm{KminK_{min}}(h[r])</tex>.
Тогда нет вхождений шаблона <tex>x</tex>, начиная с <tex>y[j \dots j']</tex> и <tex>x</tex> может быть сдвинут на <tex>\mathrm{K_{min}}(h[r])</tex> позиций вправо.
На каждой итерации цикла увеличивается либо переменная <tex>i</tex>, либо <tex>k</tex> (или переменная <tex>q</tex>, которая используется в конечном счете для обновления <tex>k</tex>). Поскольку <tex>i = 1</tex> и <tex>k = 1</tex> в начале и <tex>i < k = m + 1</tex> в конце алгоритма, количество итераций алгоритма не превосходит <tex>2 \cdot m</tex>. Следовательно функция требует <tex>O(m)</tex> времени и памяти.
Функция для построения массива <tex>\mathrm{KminK_{min}}</tex>.
'''int'''[] buildKmin('''int'''[] hmax, '''int''' m)
'''int''' kmin[m]
'''return''' kmin
Функция для построения массива <tex>\mathrm{RminR_{min}}</tex>.
'''int'''[] buildRmin('''int'''[] hmax, '''int'''[] kmin, '''int''' m)
'''int''' rmin[m]
