Изменения

left - Итератор, левая граница диапазона // изначально равна единице right - Итератор, правая граница диапазона // изначально равна длине строки lh '''lower_bound'''(left, right, value, cmp), '''upper_bound'''(left, right, value, cmp) - вспомогательная переменная для определения левой границы диапазона rg - вспомогательная переменная для определения правой границы диапазона find - функция уточнения диапазонафункции бинарного поиска из STL.

left = array.begin() right = array.end() '''for''' i = 1 '''to ''' n { lh left = n + 1 rh = 0 '''findlower_bound'''(left, right, p[i], cmp<tex>_i</tex>) right = '''upper_bound'''(left = lh , right = rh, p[i], cmp<tex>_i</tex>)

'''if''' (right - left != > 0 && right != n + 1) {

yield "No matches"  '''Бинарный поиск для уточнения диапазона''' - функция find(l, r, k) /* l - левая граница диапазона при поиске r - правая граница диапазона при поиске k - номер символа образца, с которым происходит проверка на данном шаге s - строка length - длина строки array - суффиксный массив x - индекс, стоящий по середине между l и r */ '''if''' (l > r) return x = (l + r) / 2 '''if''' (array[x] + k - 1 <= length){ '''if''' (s[array[x] + k - 1] == p[k]){ '''if''' (x < lh) lh = x '''if''' (x > rh) rh = x '''find'''(l, x - 1, k) '''find'''(x + 1, r, k) } '''else''' { '''if''' (s[array[x] + k - 1] > p[k]) { '''find'''(l, x - 1, k) } '''else''' { '''if''' (s[array[x] + k - 1] < p[k]) { '''find'''(x + 1, r, k) } } '''else''' { '''find'''(l, x - 1, k) '''find'''(x + 1, r, k) }