Изменения

Заметим, что если максимальный суффикс <tex>T[\mu..j]</tex> of <tex>T[i..j]</tex> короче, чем <tex>S_{j}^{\alpha(i,j)}</tex> (случай (b) леммы 7), алгоритм может вернуть любое <tex>p\in[i,\ j]</tex>. Далее мы предполагаем, что <tex>T[\mu..j]</tex> длиннее, чем <tex>S_{j}^{\alpha(i,\ j)}</tex> и показываем, что при этом предположении алгоритм вернёт <tex> p=\mu</tex>. Из нашего предположения свойств канонических подстрок следует, что <tex>\mu\in[i,\ r]</tex>, where <tex>r=j-|S_{j}^{\alpha(i,\ j)}|</tex>, и что длины суффиксов подстроки <tex>T[i..j]</tex>, начинающихся с позиций в промежутке <tex>[i,\ r]</tex>, отличаются не более чем в два раза.

{{Лемма