418
правок
Изменения
Нет описания правки
==Псевдокод==
'''Наивный вариант'''
'''int'''[] buildHmax('''char'''[] x, '''int''' m):
'''int''' hmax[m + 1]
'''for''' k = 1 .. m
'''int''' i = k
'''while''' x[i] == x[i - k]
i++
hmax[k] = i
return hmax
'''Улучшенный вариант'''
'''int'''[] buildHmax('''char'''[] x, '''int''' m):
'''int''' hmax[m + 1]
'''int''' i = 1
'''int''' k = 1
'''while''' k <= m
'''while''' x[i] == x[i - k]
i++;
hmax[k] = i
'''int''' q = k + 1
'''while''' hmax[q - k] + k < i
hmax[q] = hmax[q - k] + k
q++
k = q
if k == i + 1
i = k
'''return''' hmax
==Асимптотики==
* partitions the set of pattern positions into two disjoint subsets; the positions in the first set are scanned from left to right and when no mismatch occurs the positions of the second subset are scanned from right to left;
