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 :
- length(T) ~ 4 -> I have some DP idea but would appreciate if you can elaborate it more
- length(T) ~ 100
- length(T) ~ 100000
Please let me know all the available approaches.