Изменения

Пусть левая и правая границы нашего диапазона на каком-то шаге - это <tex> L </tex> и <tex> R </tex> соответственно. Допустим, что мы знаем длину общего префикса образца с суффиксами, лежащими на краях текущего диапазона: <tex> l </tex> - общий префикс образца и суффикса с левого края (<tex> l = lcp(p, array[L]) </tex>), а <tex> r </tex> - общий префикс образца и суффикса с правого края, (<tex> r = lcp(p, array[R]) </tex>). Будем поддерживать <tex> l </tex> и <tex> r </tex> после каждого уточнения границ диапазона. <br>

общий префикс образца и любого суффикса внутри диапазона не меньше <tex> m = min(l,r) </tex>. Значит <tex> m </tex> символов можно пропускать сразу, зная, что они совпадают в любом случае, и сравнивать только начиная с уже <tex> m + 1 </tex> символасимвол.

Таким образом мы применим оптимизированное сравнение строк в бинарном поиске строки «в лоб». В худшем случае, конечно, ничего мы от этого не выиграем: если искомый элемент находится на краю массива, но соседи совсем не похожи по <tex> lcp </tex>, то <tex> r </tex> (или <tex> l </tex>) будет мало каждый раз, <tex> m </tex> будет тоже мало, что сведет оптимизацию на нет. Таким образом в наихудшем случае результат будет прежним <tex> O(|p|log|s|) </tex>, но в среднем <tex> O(|p| + log|s|) </tex>.