ILoveBitches's blog

By ILoveBitches, history, 4 years ago, In English

How to calculate the number of the string S of length N, which does not contain given string T as a substring?

length(S) ~ 10000

I would like to know all the approaches for the following 2 constraints :

  1. length(T) ~ 3 -> I have some DP idea but would appreciate if you can elaborate it more
  2. length(T) ~ 100
  3. length(T) ~ 10000

EDIT: What if we want to find the number of string S which contains given string T as a substring at most K times?

Please let me know all the available approaches.

Full text and comments »

  • Vote: I like it
  • +52
  • Vote: I do not like it