Алгоритмы, дискретная математика и пр.'s Journal (original) (raw)

8:35p

Поиск нескольких подстрок Какие существуют эффективные алгоритмы для поиска в одной длинной строке нескольких похожих подстрок? Думается мне, что можно решить задачу гораздо эффективнее, чем несколько раз запустив КМП или другой быстрый алгоритм поиска одного образца.
Практическое применение очевидно - поиск словоформ или похожих слов, поиск с исправлением орфографических ошибок..
Еще интереснее - поиск сразу по нескольким регекспам. Например в Mathematica есть возможность "скомпилировать" большую таблицу правил, чтобы замены по ней выполнялись быстрее, хотя это конечно несколько другой тип регекспов..