Изменения
Нет описания правки
/*p - образец
n - длина образца
left - левая граница диапазона // изначально равна единице
right - правая граница диапазона // изначально равна длине строки
lh - вспомогательная переменная для определения левой границы диапазона
rg - вспомогательная переменная для определения правой границы диапазона
find - функция уточнения диапазона
элементы строк и массивов нумеруются с единицы*/
for i = 1 to n{ lh = n + 1 rh = 0
find(left, right, i)
left = lh right = rh } if (left != -1 0 && right != -n + 1) { // если диапазон не пуст
yield left // вывод левой границы диапазона
yield right // вывод правой границы диапазона
} else
yield "No matches" // вывод информации об отсутствии вхождений
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)
}
