TC SRM 519

p600 RequiredSubstrings

you are given a vector of string as words, and C<=6, L<=50, each word in words has length <=50. You are to find out the number of strings with length=L and contains exactly C words as substring.

To build a dp solution, you need to remember a state. Clearly you work from len=1 to L, and you need to remember what subset of words you already seen, this is only 1<<6 = 128 so no problem. But you need more than that. Ideally you want all possible prefix of length k-1, when you work on len=k, but this is too much. So you need to cut down your state. Since to have a valid word in len=k, you can separate words already in len=k-1 and words end with the kth char. To get a word end at kth char, you need to have a prefix of some words. OK, so you remember the longest suffix of your string which is a prefix of some word. char appears before that you don't care. Now your state is
dp[len][index_in_prefix][bitset_of_words_contained]

So you built an array prefix[] containing all prefixes of all words including empty string, remove duplicates. Then for each prefix and each char=a_to_z, you construct two arrays, go[p][c] is the index in prefix of the longest suffix of string prefix[p]+char(c), cover[p][c] is the bitset of words covered by string prefix[p]+char(c).

Notice that you can build a trie for all the prefix for fast check whether a given string is a prefix.