Изменения
Нет описания правки
find(x + 1, r, k)
}
=== Более быстрый поиск ===
На самом деле нам не обязательно сравнивать всю искомую строку с элементом суффиксного массива. На каждой итерации бинарного поиска мы уточняем некий диапазон, внутри которого может находиться искомый элемент. Все строки в таком диапазоне в некотором смысле похожи. А именно, у данных строк может быть общий префикс с искомой строкой, так как у тех, что остались вне диапазона, общего префикса уж точно не будет (в том смысле, что мы не рассматриваем уже обработанную часть образца как часть префикса). <br>
Допустим, мы знаем длину общего префикса оставшегося образца с краями текущего диапазона l = lcp(X,S[L]) и r = lcp(X,S[R]) для левого и правого края соответственно. Первое утверждение заключается в том, что для любой строки внутри диапазона lcp не меньше, чем минимум этих двух чисел. Если бы это было не так, то значит при неизменной начальной части префикса была бы позиция, где символ сначала совпадал бы с соответствующим символом образца, потом не совпадал, а потом снова совпадал. Это противоречило бы отсортированности диапазона. Важно хорошо проникнуться этой идеей, так как дальше мы ее будем использовать как нечто само собой разумеющееся. Второе утверждение очевидно: если общий префикс образца и любой строки внутри диапазона не меньше m=min(l,r), то m символов можно пропускать сразу, зная, что они совпадают в любом случае, и сравнивать только начиная с m+1 (и получая в результате lcp для данной строки).
