Здравствуйте, watchmaker, Вы писали:

W>Здравствуйте, Кузнец, Вы писали:

W>Алгоритм — как написано. Простейшая реализация — так:

W>

W>Пусть V - число состояний автомата

W>завести два массива A[V] и B[V]
W>инициализировать массив A значениями 0 или 1 в зависимости от того, является ли соответствующее состояние терминальным

W>для i от 1 до n:
W>   занулить массив B
W>   для каждой вершины v из [1..V]:
W>       для каждого символа s из алфавита:
W>           B[g(v, s)] += A[v]
W>   поменять массивы A и B местами
W>выдать A[root]
W>

Запрограммировал этот код, но что-то не то выдаёт, видимо я что-то напутал с терминальными вершинами.

Возьмём простой пример, пусть мы ищем слова длины 5, не содержащие одного однобуквенного подслова "a", причём для простоты пусть алфавит состоит из двух букв 'a', 'b'. Ответ в этом случае равен 1 (слов "bbbbb"). Что даст выполнение алгоритма.

Автомат для одного слова "a" состоит из двух вершин и выглядит так:

0 -a-> *1 (звёздочкой помечена терминальная вершина).

Заводим два массива A, B, начальное их состояние таково: A = {1, 0}, B = {0, 0}, делаем первый шаг, два прохода по телу цикла, первый проход прибавит ко всем вершинам, в которые можно попасть из 0-вершины, число A[0] = 0, (для символа 'a': B[1] += A[0], 'b': B[0] += A[0], B = {1, 1}), второй проход: из состояния 1 символ 'b' отправит в корень, символ 'a' отправит снова в состояние 1, то есть B[0] += A[1], B[1] += A[0], после этого шага снова B = {1, 1}. Таким образом, после первого шага (после обмена состояний массивов A, B и зануления B) имеем A = {1, 1}, B = {0, 0}. Делаем второй шаг алгоритма, формула для значений в B те же (они зависят только от автомата), а именно: B[0] = A[0] + A[1], B[1] = A[0] + A[1], и после второго шага получим A = {2, 2}, дальше значения в A будут только расти, и ответ 1 не получится никак.

Где я тут прокололся ? Такое впечатление, что не все переходы по автомату надо учитывать...