hirthwork 23.12.2012 19:23 mcabber

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

1. ulidtko 23.12.2012 21:23

чо.

2. hirthworkulidtko /1 24.12.2012 03:13 mcabber

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

Do you really want to delete ?