Обсуждение:Алгоритм Ахо — Корасик

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Время работы пропорционально суммарной длине строк словаря и строки поиска, то есть линейно.[править код]

Это неверно. Время работы также пропорционально размеру ответа,т.е. оно равно O(n+m+ans), где n - длина строки, в которой мы ищем, m - сумма длин строк, которые мы ищем, ans - размер ответа. 79.126.2.64 14:08, 5 марта 2008 (UTC)asil

Да, правда, забыл добавить.

Compilator 16:57, 5 марта 2008 (UTC)

Поэтому суммарное время работы может быть квадратичным (например, если в строке «ааааааа» мы ищем слова «а», «аа», «ааа», …).[править код]

Не совсем понятен смысл этого комментария, нельзя же в принципе сделать время работы не квадратичным, хотя бы потому что вывести ответ нужно.

95.84.11.46 11:24, 27 марта 2009 (UTC)

Это зависит от того, что делается когда обнаружен один из образцов. вовсе не обязательно они будут выводиться. Так что не надо тут про квадратичность. Gvsmirnov 12:29, 13 июня 2009 (UTC)

Функция Search[править код]

Вам не кажется, что эта функция не обрабатывает все слова, которые являются суффиксами найденного (например, поиск слов "he", "she" в тексте "she" обработает только "she")? Я бы написал что-то вроде такого (прошу прощения за кривую разметку, не понимаю, почему оно не захватывает сигнатуру):

void Search(const char* str, Callback callback) {

       BorNode* current_node = &root;
       for(int pos = 1; *str; ++str, ++pos)
       {
           map<char, BorNode*>::iterator iter = current_node->links.find(*str);
           while(iter == current_node->links.end())
           {
               current_node = current_node->fail;
               iter = current_node->links.find(*str);
               if(current_node == current_node->fail)
                   break;
           }
           if(iter != current_node->links.end())
           {
               current_node = iter->second;

           	if(current_node->out >= 0)
                {   
                   callback(words[current_node->out].c_str(), pos - words[current_node->out].length(), pos - 1);
                   BorNode* tmp = current_node->fail;
                   while(tmp != &root)
                   {
                    if(tmp->out>=0)
                       {// обработка слова, которое является суффиксом первого найденного }
                    tmp = tmp->fail;
                   }
                }
           }
       }
   }

188.115.158.15 17:02, 4 февраля 2011 (UTC)