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.

How to update F[i][k+1]?