ALGO IS HERE:

1. Remove all words which contain some other word as a substring. They do not affect anything, but make further things more difficult.

2. Build characters tree from forbidden words. E.g. for set "aabc, abd, bcd" it will be like that:
root(a(a(b(c)),b(d)),b(c(d)))

positions in this tree will represent history (recent placed letters) and its size will be <= 100 (total amount of letters in all forbidden words)

A path from root to node is safe if it does not end in a leaf (otherwise you're in jail for 10 years). Any sub-paths of a safe path are also safe because we removed all words which could lead to such paths. So, we have a good test for path safety - it shouldn't be a leaf, and that's enough.

While we place letters, we are allowed to make only safe steps - we can't step into a leaf.

If we attempt to perform a step outside of the tree, we should apply 1st postfix of history to that tree to find where will we get after forgetting that least recent placed letter. For example, if the string 'aabce' falls out from the tree after 'aab' (i.e. there is no forbidden word starting with 'aabc'), then we will search for 'abce' (1st postfix of 'aabce') in the same manner, recursively. All this information can be precalculated (which state leads where after adding some particular letter). It's like prebuilding automaton for multi-substring search and then calculate number of programs which do not lead to terminal states.

This gave me AC in 0.031 sec and final understanding of KMP which I used blindly before :)

Edited by author 05.08.2008 04:24