275
правок
Изменения
→Продление суффиксов
== Продление суффиксов ==
Ниже приведены возможные случаи, которые могут возникнуть при добавлении символа <tex>s_{i}</tex> ко всем суффиксам префикса <tex>s[1..i-1]</tex>.
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=7075%
!style="background:#f2f2f2"|Случай
!style="background:#f2f2f2"|Правило
|-
|style="background:#ffffff"|''2.2 Ответвление''
|style="background:#ffffff"|Пусть суффикс <tex>s[k..i-1]</tex> заканчивается на ребре, и <tex>t[1..lp-1]</tex> совпадает с концом <tex>s[k..i-1]</tex>. Если и <tex>t_{lp}\ne s_{i}</tex>. Разобьем текущее ребро новой вершиной на <tex>t[1..p-1]</tex> и <tex>t[p..l]</tex>, где <tex>l</tex> {{---}} длина метки ребра, то создадим новую вершину в месте неравенства и добавим подвесим к ней еще одного ребенка с дугой, помеченной <tex>s_{i}</tex>.
|style="background:#ffffff"|[[Файл:Case1.png]]
|-
