найти номер строки без определенной подстроки

Question

проблема задана N (1 < = N < = 10) строка длиной не более 6, как я могу рассчитать число строк с длиной L (1 < = L < = 1000000) без какой-либо из n строк в качестве подстроки. Каждая строка содержит только прописную букву.

лучший, я могу думать, использует dp L * (26^5), но я не думаю, что это пройдет срок :(может кто-нибудь поделиться какой-то идеей? Btw вот оригинальная проблема http://www.spoj.com/problems/GEN/, если вы этого не сделаете понять, что я пишу выше

Answer 1

Во-первых, создать НКА (недетерминированных конечных автоматов), который принимает все «плохие» строки. Затем преобразовать его в ДКА, используя конструкцию подмножества. Затем вычислить дополнение этого DFA.

Подсчитать количество строк, принятых DFA, довольно просто: количество строк длины k + 1, заканчивающихся в заданном состоянии, может быть вычислено суммированием числа строк длины k, заканчивающихся в каждом предпродаже ssor.

Это, скорее всего, произойдет вовремя, если у вас будет достойная реализация. Однако, если это не так, вы можете использовать автомат от предварительной обработки Aho-Corasick вместо DFA.