Изменения
Нет описания правки
==Улучшение бинарного поиска==
При двоичном поиске обозначим левую и правую границы текущего интервала как <tex> L </tex> и <tex> R </tex> соответственно. Изначально <tex> L = 0 </tex>, <tex> R = |S| - 1 </tex>. На каждой итерации будем сравнивать образец <tex> P </tex> с суффиксом <tex> sufArray[(L + R) / 2] </tex>. Обозначим за <tex> left </tex> длину общего префикса <tex> P </tex> и <tex> sufArray[L] </tex>, а за <tex> right </tex> длину общего префикса <tex> P </tex> и <tex> sufArray[R] </tex>. Также обозначим за <tex> minRange </tex> минимум из <tex> left </tex> и <tex> right </tex>. Значение <tex> minRange </tex> будем поддерживать на каждой итерации двоичного поиска. Теперь, зная <tex> minRange </tex>, можно начинать сравнение образца <tex> P </tex> с суффиксом <tex> sufArray[(L + R) / 2] </tex>, начиная с <tex> minRange + 1 </tex> символа. Это возможно, так как для любого суффикса из нашей границы от <tex> L </tex> до <tex> R </tex> первые <tex> minRange </tex> символов совпадают. Если бы это было не так, то в суффиксном массиве в границе от <tex> L </tex> до <tex> R </tex> были бы суффиксы, которые сначала имеют <tex> minRange </tex> совпадений, затем не имеют, а затем снова имеют, что говорит о неправильном построении суффиксного массива. <br>
При таком поиске время работы равно <tex> O(|P| + log|S|) </tex>.
