Изменения

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