Редактирование: Алгоритм Ахо-Корасик
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 15: | Строка 15: | ||
Обозначим за <tex>[u]</tex> слово, приводящее в вершину <tex>u</tex> в боре.<br /> | Обозначим за <tex>[u]</tex> слово, приводящее в вершину <tex>u</tex> в боре.<br /> | ||
Узлы бора можно понимать как состояния [[Детерминированные_конечные_автоматы | автомата]], а корень как начальное состояние.<br /> | Узлы бора можно понимать как состояния [[Детерминированные_конечные_автоматы | автомата]], а корень как начальное состояние.<br /> | ||
− | Узлы бора, в которых заканчиваются | + | Узлы бора, в которых заканчиваются строк, становятся терминалами.<br /> |
Для переходов по автомату заведём в узлах несколько функций:<br /> | Для переходов по автомату заведём в узлах несколько функций:<br /> | ||
*<tex>\mathrm{parent}(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>;<br /> | *<tex>\mathrm{parent}(u)</tex> {{---}} возвращает родителя вершины <tex>u</tex>;<br /> |