Изменения

Рассмотрим построение суффиксного автомата для строки <tex>abcb</tex>{| class = "wikitable"! Изображение !! Описание|-|[[Файл:Suffix_automaton_s1. Серыми стрелками показаны суффиксные ссылкиpng|x180px|center|Шаг 1.]]# |Изначально автомат состоит из одного начального состояния. <tex>\mathrm{last} = 0, \mathrm{len(0)} = 0</tex>.<br><br>|-|[[Файл:Suffix_automaton_s1Suffix_automaton_s2.png|x180px|thumb|center|Шаг 12.]]<br># |Добавляем символ <tex>a</tex>. Создаем состояние <tex>1</tex>. Переходов из начального состояния по символу <tex>a</tex> нет, перейти по суффиксным ссылкам некуда, значит добавим суффиксную ссылку <tex>\mathrm{link_{1}} = 0</tex>. <tex>\mathrm{last} = 1, \mathrm{len(1)} = 1</tex>.<br><br>|-|[[Файл:Suffix_automaton_s2Suffix_automaton_s3.png|x180px|thumb|center|Шаг 23.]]<br># |Добавляем символ <tex>b</tex>. Создаем состояние <tex>2</tex>. Добавим переход из <tex>1</tex>, откатимся по суффиксной ссылке и добавим переход из <tex>0</tex>. Добавим суффиксную ссылку <tex>\mathrm{link_{2}} = 0</tex>. <tex>\mathrm{last} = 2, \mathrm{len(2)} = 2</tex>.<br><br>|-|[[Файл:Suffix_automaton_s3Suffix_automaton_s4.png|x180px|thumb|center|Шаг 34.]]<br># |Аналогично добавим символ <tex>c</tex> и обновим автомат. <tex>\mathrm{last} = 3, \mathrm{len(3)} = 3</tex>.<br><br>|-|[[Файл:Suffix_automaton_s4Suffix_automaton_s5.png|x180px|thumb|center|Шаг 45.]]<br># |Добавляем символ <tex>b</tex>. Добавим переход из <tex>3</tex> и перейдем по суффиксной ссылке в начальное состояние. Из состояния <tex>0</tex> существует переход по символу <tex>b</tex>.<br><br>|-|[[Файл:Suffix_automaton_s5Suffix_automaton_s6.png|x180px|thumb|center|Шаг 56.]]<br># |Рассмотрим состояние <tex>2</tex>, куда существует переход. Имеем <tex>\mathrm{len(0)} + 1 \neq \mathrm{len(2)}</tex>.## Создаем новое состояние <tex>5</tex>.## Копируем в него все суффиксные ссылки и переходы из <tex>2</tex> и присвоим <tex>\mathrm{len(5)} = \mathrm{len(0)} + 1 = 1</tex>.## Перенаправим суффиксную ссылку из <tex>2</tex> в <tex>5</tex> и добавим ссылку из <tex>4</tex> в <tex>5</tex>. Перенаправим переход <tex>0 \rightarrow 2</tex> в состояние <tex>5</tex>.<br><br>|-|[[Файл:Suffix_automaton_s6Suffix_automaton_s7.png|x180px|thumb|center|Шаг 67.]]<br># |Построение автомата завершено. Чтобы пометить терминальные вершины, найдём состояние, которое принимает строку <tex>abcb</tex> и пройдём по суффиксным ссылкам, помечая все посещенные состояния терминальными.<br><br>[[Файл:Suffix_automaton_s7.png|x180px-|thumb|center|Шаг 7.]]}