Изменения

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