Изменения
→Более быстрый поиск
=== Более быстрый поиск ===
На <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>
