Изменения

На самом деле нам не обязательно сравнивать всю искомую строку с элементом элементами суффиксного массива. На каждой итерации бинарного поиска мы уточняем некий диапазон, внутри которого может находиться искомый элемент. Все строки в таком диапазоне в некотором смысле похожи. А именно, у данных строк может быть общий префикс с искомой строкой, так как у тех, что остались вне диапазона, общего префикса уж точно не будет (в том смысле, что мы не рассматриваем уже обработанную часть образца как часть префикса). <br>

Пусть границы нашего диапазона на каком-то шаге - это L и R. Допустим, мы знаем длину общего префикса оставшегося образца с краями текущего диапазона : l - общий префикс образца и левого края, r - общий префикс образца и правого края, где l = lcp(Xp,Sarray[L]) и , r = lcp(Xp,Sarray[R]) для левого и правого края соответственно(lcp - longest common prefix). Тогда справедливо сделать пару утверждений. <br>Первое утверждение заключается в том, что для любой строки внутри диапазона lcp не меньше, чем минимум этих двух чиселиз l и r. Если бы это было не так, то значит при неизменной начальной части префикса была бы позиция, где символ сначала совпадал бы с соответствующим символом образца, потом не совпадал, а потом снова совпадал. Это противоречило бы отсортированности диапазона. Важно хорошо проникнуться этой идеей, так как дальше мы ее будем использовать как нечто само собой разумеющееся. Второе утверждение очевидно: если общий префикс образца и любой строки внутри диапазона не меньше m=min(l,r), то m символов можно пропускать сразу, зная, что они совпадают в любом случае, и сравнивать только начиная с m+1 (и получая в результате lcp для данной строки)символа.