hirthwork 23.12.2012 19:23 mcabber

внезапно мне открылось откровение. Алгоритмы типа Бойера-Мура-Хорспула не
обязаны просматривать все символы строки в которой производится поиск. Т.е.
решение «в лоб» на конечном автомате полностью просасывает столь примитивному
алгоритму. такие дела, да.

fsm, programming, slowpoke
#tfghgi
re 2 comments !recommend ~bookmark Ssubscribe
1. ulidtko 23.12.2012 21:23

чо.

#tfghgi/1
rereply
2. hirthwork → ulidtko /1 24.12.2012 03:13 mcabber

если искать подстроку в строке конечным автоматом, то точной оценкой сложности будет являться O(m) — длина строки в которой ищем, а если тупым алгоритмом Бойера-Мура-Хорспула, то в лучшем случае алгоритм отработает за O((m/n) + n), где n — длина искомой строки.

#tfghgi/2
rereply
Do you really want to delete ?