Изменения

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

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

Нет изменений в размере, 19 январь
Пример автомата Ахо-Корасик: Replace tex with <code> because it is more suitable for strings and quotes were separated with extra spaces
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
Суффиксная ссылка для каждой вершины <tex>u</tex> — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине <tex>u</tex>. Единственный особый случай — корень бора: для удобства суффиксную ссылку из него проведём в себя же. Например, для вершины <tex>5</tex> с соответствующей ей строкой <texcode>"she"</texcode> максимальным подходящим суффиксом является строка <texcode>"he"</texcode>. Видим, что такая строка заканчивается в вершине <tex>2</tex>. Следовательно суффиксной ссылкой вершины для <tex>5</tex> является вершина <tex>2</tex> .
===Шаг 3. Построение сжатых суффиксных ссылок ===
Анонимный участник

Навигация