Number of Strings without containing given string as substring?

Revision en5, by ILoveBitches, 2020-04-29 22:09:00

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.

Tags #dp, difficult, #combination, #combinatorics

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English ILoveBitches 2020-04-29 22:09:00 4 Tiny change: ' 10000\n\nEDIT: What if ' -> ' 10000\n\n**EDIT**: What if '
en4 English ILoveBitches 2020-04-29 22:08:34 118
en3 English ILoveBitches 2020-04-29 21:33:59 3
en2 English ILoveBitches 2020-04-29 21:32:05 2 Tiny change: ' ~ 10000\nI would ' -> ' ~ 10000\n\nI would '
en1 English ILoveBitches 2020-04-29 21:31:36 463 Initial revision (published)