418
правок
Изменения
→Псевдокод
hmax[k] = i
return hmax
Явная реализация по определению, очевидно, работает за <tex>O(m^2)</tex> и требует <tex>O(m)</tex> памяти.
'''Улучшенный вариант'''
'''int'''[] buildHmax('''char'''[] x, '''int''' m):
'''int''' hmax[m + 1]
i = k
'''return''' hmax
На каждой итерации цикла увеличивается либо переменная <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>Kmin</tex>.
'''int'''[] buildKmin('''int'''[] hmax, '''int''' m)
'''int''' kmin[m]
'''for''' i = m .. 1
'''if''' hmax[i] < m
kmin[hmax[i]] = i
'''return''' kmin
Функция для построения массива <tex>Rmin</tex>.
'''int'''[] buildRmin('''int'''[] hmax, '''int'''[] kmin, '''int''' m)
'''int''' rmin[m]
'''int''' r = 0
'''for''' i = m - 1 .. 0
'''if''' hmax[i + 1] == m
r = i + 1
'''if''' kmin[i] == 0
rmin[i] = r
'''else'''
rmin[i] = 0
return rmin
==Асимптотики==
