Обсуждение:Алгоритм Ахо — Корасик
Проект «Информационные технологии» (уровень IV, важность для проекта средняя)
Эта статья тематически связана с вики-проектом «Информационные технологии», цель которого — создание и улучшение статей по темам, связанным с информационными технологиями. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями. |
Время работы пропорционально суммарной длине строк словаря и строки поиска, то есть линейно.[править код]
Это неверно. Время работы также пропорционально размеру ответа,т.е. оно равно 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;
}
}
}
}
}