Изменения

Пусть границы нашего диапазона на каком-то шаге - это L и R. Допустим мы знаем длину общего префикса образца с краями текущего диапазона: l - общий префикс образца и левого края, r - общий префикс образца и правого края, где l = lcp(p, array[L]), r = lcp(p, array[R]) (lcp - longest common prefix). Тогда справедливо сделать пару утверждений. <br>

Первое утверждение заключается в том, что для любой строки внутри диапазона lcp не меньше, чем минимум из l и r. Если бы это было не так, то значит при неизменной начальной части префикса была бы позиция, где символ сначала совпадал бы с соответствующим символом образца, потом не совпадал, а потом снова совпадал. Это противоречило бы отсортированности диапазона. Важно хорошо проникнуться этой идеей, так как дальше мы ее будем использовать как нечто само собой разумеющееся. Второе утверждение очевидно: если общий префикс образца и любой строки внутри диапазона не меньше m = min(l,r), то m символов можно пропускать сразу, зная, что они совпадают в любом случае, и сравнивать только начиная с m + 1 символа.