Изменения

Перейти к: навигация, поиск

Алгоритм Ахо-Корасик

13 байт добавлено, 19 январь
Пример автомата Ахо-Корасик: Replace back to tex, to the same style as in the beginning of the article
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
Суффиксная ссылка для каждой вершины <tex>u</tex> — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине <tex>u</tex>. Единственный особый случай — корень бора: для удобства суффиксную ссылку из него проведём в себя же. Например, для вершины <tex>5</tex> с соответствующей ей строкой <codetex>\textbf{she}</codetex> максимальным подходящим суффиксом является строка <codetex>\textbf{he}</codetex>. Видим, что такая строка заканчивается в вершине <tex>2</tex>. Следовательно суффиксной ссылкой вершины для <tex>5</tex> является вершина <tex>2</tex> .
===Шаг 3. Построение сжатых суффиксных ссылок ===
Анонимный участник

Навигация