Изменения

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