13
правок
Изменения
→Поиск границ диапазона ответов
[[Файл:left.png]]
Если <tex> l < r </tex>, то действия аналогичны.Так же три случая:# <tex> r < m_r </tex>. Сдвигаем <tex> R </tex> в <tex> M </tex>. Значение <tex> r </tex> не изменяется.# <tex> r = m_r </tex>. Считаем <tex> lcp </tex> для образца и суффикса, стоящего в позиции <tex> M </tex>, начиная с позиции <tex> r </tex>. # <tex> r > m_r </tex>. Сдвигаем <tex> L </tex> в <tex> M </tex>, <tex> l = m_r </tex>. [[Файл:Right2.png]]
Бинарный поиск будет работать до тех пор, пока <tex> R - L > 1 </tex>. После этого можно присвоить левой границе диапазона ответов <tex> L_p = R </tex> и переходить к поиску правой границы диапазона ответов <tex> R_p </tex>.
