Изменения
→Псевдокод
Сравнения < , > , == , <= , >= при применении к строкам
означают полное лексикографическое сравнение строк.
Функция '''lcp'''<mathtex>_z</mathtex>(s, p) ищет количество совпадений символов
строк s и p начиная с позиции z.
n - длина строки s.
r = '''lcp'''(p, s[array[n-1]])
'''if''' (l == w or p < s[array[0]])
L<mathtex>_p</mathtex> = 0
'''else''' if (p > s[array[n-1])
L<mathtex>_p</mathtex> = n
'''else''' {
L = 0
'''while''' (R - L > 1) '''do''' {
M = (L + R)/2
m<mathtex>_l</mathtex> = lcp(array[L],array[M]) m<mathtex>_r</mathtex> = lcp(array[M],array[R])
'''if''' (l >= r)
'''if''' (m<mathtex>_l</mathtex> >= l) m = l + '''lcp'''<mathtex>_l</mathtex>(s[array[M]], p)
'''else'''
m = m<mathtex>_l</mathtex>
'''else'''
'''if''' (m<mathtex>_r</mathtex> >= r) m = r + lcp<mathtex>_r</mathtex>(s[array[M]], p)
'''else'''
m = m<mathtex>_r</mathtex> '''if''' (m == w || p <=<mathtex>_m</mathtex> s[array[M]]){
R = M
r = m
}
}
L<mathtex>_p</mathtex> = R
}
