Изменения

Когда используется 3-е правило продления суффикса, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать текущую итерацию после первого же использования этого правила. Так как лист навсегда останется листом, зададим метку ребра ведущего в этот лист как <tex>ts[i..n]</tex>, где <tex>n</tex> {{---}} это длина исходного текста. На следующих итерациях к этому ребру может применяться правило ответвления, но при этом будет меняться только левый(начальный) индекс <tex>i</tex>. Таким образом мы сможем удлинять все суффиксы, заканчивающиеся в листах за <tex>O(1)</tex>.