Изменения

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

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

264 байта добавлено, 00:15, 29 мая 2016
Пример автомата Ахо-Корасик
Пунктиром обозначены суффиксные ссылки. Из вершин, для которых они не показаны, суффиксные ссылки идут в корень.
Суффиксная ссылка для каждой вершины <tex>u</tex> — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине <tex>u</tex>. Единственный особый случай — корень бора; для удобства суффиксную ссылку из него проведём в себя же. Например, для вершины <tex>5</tex> с соответствующей ей строкой <tex>"she"</tex> суффиксной ссылкой максимальным суффиксом является вершина строка <tex>2"she"</tex> с соответствующей ей строкой , но такой строки больше в нашем автомате нет. Возьмем второй по длине суффикс <tex>"he"</tex>. Видим, которая и что такая строка заканчивается в вершине <tex>2</tex>. Следовательно суффиксной ссылкой вершины для <tex>5</tex> является максимальным суффиксомвершина <tex>2</tex> .
===Шаг 3. Построение сжатых суффиксных ссылок ===
Анонимный участник

Навигация