Build an aho-corasick automaton on the given N ‘bad’ strings, and then let dp[state][i] be the maximum answer you can get using the first i characters of S, and when you’re at state in the automaton. There are two transitions - either you use the i-th character, or you don’t.
Use the automaton to check whether any state corresponds to the end of some bad string and don’t consider the dp at such states.
The answer is the maximum of dp[state][n] over all valid states.
3 Likes