Изменения
→Псевдокод
===Псевдокод===
Поиск левой границы ответов <tex> L_p </tex>.
/*
Массивы и строки нумеруются с нуля.
Сравнения <<math>_z </math> , ><math>_z </math> , =<math>_z </math> , <=<math>_z </math> , >=<math>_z </math> означают
лексикографическое сравнение двух строк по их первым z символам.
Сравнения < , > , == , <= , >= при применении к строкам
означают полное лексикографическое сравнение строк.
Функция lcp(s<math>_z</math>, p<math>_z</math>) означает поиск максимального общего префикса
строк s и p начиная с позиции z.
n - длина строки s.
*/
l = lcp(p, s[array[0]])
r = lcp(p, s[array[n-1]])
if (l == |p| or p < s[array[0]])
L<math>_p</math> = 0
else if (p > s[array[n-1])
L<math>_p</math> = n
else {
L = 0
R = n - 1
while (R - L > 1) do {
M = (L + R)/2 </math>
m<math>_l</math> = lcp(array[L],array[M])
m<math>_r</math> = lcp(array[M],array[R])
if (l >= r)
if (m<math>_l</math> >= l)
m = l + lcp(s[array[M]]<math>_l</math>, p<math>_l</math>)
else
m = m<math>_l</math>
else
if (m<math>_r</math> >= r)
m = r + lcp(s[array[M]]<math>_r</math>, p<math>_r</math>)
else
m = m<math>_r</math>
if (m == p || p <=<math>_m</math> s[array[M]]){
R = M
r = m
} else {
L = M
l = m
}
}
L<math>_p</math> = R
}
==Литература==
* http://habrahabr.ru/blogs/algorithm/115346/
*U. Manber and G. Mayers. "Suffix arrays: A new method for on-line string searches"
