|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ihor Bobak 2:5020/400 21 May 2001 20:41:20
To : All
Subject : Поиск набора слов в тексте с помощью конечных автоматов
--------------------------------------------------------------------------------
Для нахождения количества вхождений слова P в текст Т
существует классический алгоритм, использующий конечный автомат
(алгоритм хорошо описан в книге Кормена "Алгоритмы: построение и анализ").
Hедавно, на Всеукраинской олимпиаде по программированию
(которая проходила в апреле, в Виннице) была поставлена
более общая задача:
дано набор слов (словарь) P1, P2, ... PN (N<=200, |Pi|<=20) и
длинный текст T (|T|<=2000000). Для каждого слова из словаря
нужно найти количество вхождений в текст.
По коду суддейского (эталонного) решения видно, что строится
автомат, а потом посимвольно читается текст и обрабатывается
этим автоматом. Hо из-за сложности кода я не могу понять принцип
построения такого автомата.
Кто-нибудь знает алгоритм построения конечного автомата для
этой задачи? Буду благодарен за посылание на литературу,
линки, и пр.
С уважением,
Игорь Бобак
--- ifmail v.2.15dev5
* Origin: MTU-Intel ISP (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
