find number of string without certain substring

Question

the problem is given N (1 <= N <= 10) string with length no more than 6, how can i calculate number of string with length L (1 <= L <= 1000000) without any of the n string as the substring. every string only contain uppercase letter.

the best i can think is using dp L * (26^5) but i don't think this will pass the time limit :( can anyone share some idea ? btw here's the original problem http://www.spoj.com/problems/GEN/ if you don't understand what i write above

Answer 1

First, create an NFA (nondeterministic finite automaton) that accepts all of the "bad" strings. Then convert it to a DFA using the subset construction. Then compute the complement of that DFA.

Counting the number of strings accepted by a DFA is rather straightforward; the number of strings of length k+1 ending in a given state can be computed by summing the number of strings of length k ending in each predecessor state.

This will likely run in time if you have a decent implementation. However, if it doesn't, you can use the automaton from Aho-Corasick preprocessing instead of the DFA.