Доброго времени суток
Может вопрос несколько не по алгоритмам но все-же

Задача выяснить является ли некая последовательность символов словом. Для этого сравниваю последовательность с хешированным словарем.
Последовательностей много.
Основная задача уменьшить их количество до момента, когда нужно сравнивать.
Например можно сразу сказать что слово не является последовательность содержащая "ЪЬ","[гласная]Ь" и т.д. Где можно раздобыть подобные "подстроки" или может есть другие способы определения слов без использования словаря?

Если при выделении последовательности считается и её длина (например, для каких-то иных нужд), т.е. если длину строки дополнительно считать не надо будет, то можно словарь разделить на подсловари, в каждом из которых будут слова одинаковой длины, и поиск запускать на подсловаре со словами совпадающей длины. И, думаю, если подетальнее залезть в потроха Вашей задачи, то можно будет придумать другие способы ускорения поиска, если не сработает этот.

Ну а по выделению недопустимых буквосочетаний. На хорошо вычитанном корректорами корпусе текстов (например, на старых текстах из библиотеки Мошкова) можно построить матрицу частот переходов от буквы к букве, и клетки матрицы с нулевыми значениями частот будут соответствовать нереализовавшимся в русском языке буквосочетаниям из двух букв. Для трехбуквенных сочетаний - всё делается аналогично, но на трехмерной матрице. 

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

PS. Вообще-то, Ваша задача кажется настолько быстро считаемой, что надо просто привлечь квалифицированного программиста и понять, где и что можно экономить, и за счет чего. Ибо я часто сталкивался с примерами "ошибок в ДНК". Например, для некоторой задачи обработки текстов одна девушка вместо алгоритма сложностью О(N), требующего, правда, удвоения объема используемой памяти по сравнению с минимумом, взяла обходящийся минимумом памяти алгоритм сложностью О(N^2) - а в итоге получила тормоза расчетов, что было бы изначально очевидно любому грамотному алгоритмисту-программисту.

Делается алгоритм хода компьютера в игре Балда. 
Хм, насчет разделения словаря интрересно, как-то крутилось в голове, но казалось очень накладным, попробую. У меня в основном вся оптимизация во время рекурсивного поиска этих подстрок, останавливаю поиск на несложных правилах типа "если несколько согласных/гласных подряд", "начинается не так", "длинна цепочки больше N символов" и другие очевидные варианты, также пытаюсь соптимизировать на таскаемых за собой координатах клеток доски для проверки некоторых условий(исходя из правил игры). На небольшом словаре(10к слов) работает довольно быстро(2-3 секунды при полной доске), но поглядывая на различные "решалки Балды" хочу чтобы компьютер думал не более секунды.

Это сообщение отредактировал(а) Sosed - 25.5.2010, 16:32

Профилировщиком пользовались? Или методом тыка самое тормознутое место программы пытаетесь вычислить?

Попытайтесь без рекурсии обойтись - зачем тратить лишнее время на кучу вызовов функции с передачей ей аргументов? 

Найти все вхождения строки S длиной m во множество строк можно с помощью обобщённого суффиксного дерева (generalized suffix tree) за O(m+k), где k — количество таких вхождений. При этом алгоритм можно сделать инкрементальным: допустим, вы получили положительный результат для последовательности из n символов на предполагаемом маршруте, тогда проверка следующего символа будет значительно быстрее, чем проверка строки из n+1 символов «с нуля».