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