271
правка
Изменения
Нет описания правки
На самом деле нам не обязательно сравнивать всю искомую строку с элементами суффиксного массива. На каждой итерации бинарного поиска мы уточняем некий диапазон, внутри которого может находиться искомый элемент. Все строки в таком диапазоне в некотором смысле похожи. А именно, у данных строк может быть общий префикс с искомой строкой, так как у тех, что остались вне диапазона, общего префикса уж точно не будет (в том смысле, что мы не рассматриваем уже обработанную часть образца как часть префикса). <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> символа.
