|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ivan Boldyrev 2:5080/1003 11 Jul 2003 21:37:01
To : "Dmitriy Krylov"
Subject : Re: Хитрый поиск подстроки
--------------------------------------------------------------------------------
"DK" == Dmitriy Krylov writes:
DK>>> В дереве Кнута дуги размечены буквами алфавита. Вершины
DK>>> помечаются признаком "принадлежит словарю/не принадлежит
DK>>> словарю".
IB>> А разве это не является частным случаем конечного автомата?
DK> Получается так. Возможно, представление в виде конечного автомата
DK> будет более компактным. Тогда какова его структура?
Дуги так же помечены буквами, вершины являются состояниями, если
вершина в дереве была помечена как "принадлежит", то она
заключительная, а если нет -- то нет :)
К получившимуся КА можно потом применить процедуру построения
минимального КА (см. книги Ахо и Ульмана (и ещё кого-то, не помню) по
компиляторам).
--
Ivan Boldyrev
"Сборка японского велосипеда требует величайшего спокойствия духа."
--- ifmail v.2.15dev5
* Origin: this field is intentionally left blank (2:5080/1003@fidonet)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
