275
правок
Изменения
м
→Использование суффиксных ссылок
Рассмотрим один такой переход, пусть мы только что продлили суффикс <tex>s[j..i-1]</tex> до суффикса <tex>s[j..i]</tex>. Теперь с помощью построенных ссылок найдем конец суффикса <tex>s[j+1..i-1]</tex>, чтобы продлить его до суффикса <tex>s[j+1..i]</tex>. Пройдем вверх по дереву до ближайшей внутренней вершины <tex>v</tex>, в которую ведет путь, помеченный <tex>s[j..r]</tex>. У вершины <tex>v</tex> есть суффиксная ссылка, так как ссылка для внутренней вершины строится внутри фазы создания этой вершины. Пусть суффиксная ссылка ведет в вершину <tex>u</tex>, которой соответствует путь с пометкой <tex>s[j+1..r]</tex>. Теперь пройдем от вершины <tex>u</tex> вниз по дереву к концу суффикса <tex>s[j+1..i-1]</tex>, и сделаем продление до суффикса <tex>s[j+1..i]</tex>.
Мы знаем сколько символов просмотрели на ребре ведущем вершину, из которой мы поднялись перед тем как сделать переход по суффиксной ссылке. Поэтому не сложно осознать, что при спуске к концу <tex>s[j+1..i-1]</tex> суффикса не нужно просматривать все символы, а можно сразу перейти к проверке существования перехода по символу <tex>s_i</tex> символу.
=== Построение суффиксных ссылок ===
