Изменения
→Более быстрый поиск
На <tex> i </tex>-ом шаге алгоритма мы мы определяем диапазон, в котором <tex> i </tex> первых символов образца и суффиксов диапазона совпадают. На самом деле нам не обязательно на каждом шаге проверять лишь один новый символ символ. Воспользуемся <tex> lcp </tex>(longest common prefix). <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>. Будем поддерживать <tex> l </tex> и <tex> r </tex> после каждого уточнения границ диапазона. <br>
Для каждой пары строк внутри текущего диапазона их lcp не меньше, чем минимум из <tex> l </tex> и <tex> r </tex>. Если бы это было не так, то значит при неизменной начальной части префикса была возникла бы позицияситуация, где символ сначала совпадал когда между двумя суффиксами, lcp для которых равно минимуму из <tex> l </tex> и <tex> r </tex>, лежал бы суффикс, lcp которого с соответствующим символом образца, потом не совпадалкаким-то из этих двух суффиксов было бы меньше, а потом снова совпадал. Это что противоречило бы отсортированности диапазона. Важно хорошо проникнуться этой идеей, так как дальше мы ее будем использовать как нечто само собой разумеющееся.<br> Второе утверждение очевидно: А если общий префикс образца и любой строки внутри диапазона не меньше <tex> m = min(l,r) </tex>, то <tex> m </tex> символов можно пропускать сразу, зная, что они совпадают в любом случае, и сравнивать только начиная с <tex> m + 1 </tex> символа.
[[Файл:pic.png|450px]]
