Number of Strings without containing given string as substring? - Codeforces

→ Pay attention

Before contest
Educational Codeforces Round 173 (Rated for Div. 2)
35:03:34
Register now »

→ Streams

CF Edu Round 173 Solution Discussion

By aryanc403

Before stream 37:13:34

View all →

→ Top rated

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Countries | Cities | Organizations

→ Top contributors

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	Dominater069	154
8	awoo	154
10	luogu_official	151

View all →

→ Find user

→ Recent actions

Detailed →

Number of Strings without containing given string as substring?

Revision en1, by ILoveBitches, 2020-04-29 21:31:36

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.

Tags

#dp, difficult, #combination, #combinatorics

History

Revisions

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