ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1158. Censored!

Don't panic!
Posted by Otrebus 20 Dec 2015 05:14
Some have claimed that this is a very difficult problem. Not true! There is a reasonably simple and very fast DP-solution to this problem. No string algorithms are required beyond the naive ones that every non-programmer knows.

Hint: Store the solution for sentences of length k in A[k], and store the number of strings that end with some forbidden word i (0 < i < P), but does not contain any other forbidden words as substrings in F[i][k]. Then construct the solution from A[k] to A[k+1], updating F[i][k+1] as well for each i. For each new character that you tuck onto the end of a valid string of length k, you get A[k] more valid strings, except those that end with a forbidden word, so those strings need to be removed. But make sure you don't remove stuff that you've assumed that you already removed earlier in the string - that's where F[i][k] comes in handy.
Re: Don't panic!
Posted by HomlyJ 6 Aug 2019 12:47
How to update F[i][k+1]?