Please read the new rule regarding the restriction on the use of AI tools. ×

Required Substrings problem on CSES

Revision en3, by harsh-apcr, 2023-11-03 13:00:33

Can someone explain how to solve Required Substring problem in CSES : https://cses.fi/problemset/task/1112

Your task is to calculate the number of strings of length n having a given pattern of length m as their substring. All strings consist of characters A–Z.

My approach :

I was thinking of some dp approach and instead of counting the required quantity directly, I'd count the complement and subtract from $$$26^n$$$

But, I am stuck with this approach, I thought of the following recursion

$$$dp(i, j) = # of strings of length i not containing s, whose suffix of length i is a prefix of s (i.e. s_1\ldots s_j)$$$

$$$dp(i, j) = \sum_{j'\in S} dp(i-1, j') + dp(i-1, j-1)$$$, where $$$S$$$ = set of all $$$j'$$$ such that $$$s_1 \ldots s_{j'}$$$ has a prefix of length $$$j-1$$$ which is also its suffix

and then finally compute : $$$dp(i) = 26*dp(i-1)-dp(i-1,m-1)$$$ (supposed to count strings of length i not containing s)

but I cannot figure out how to instantiate the base case $$$dp(i, 0)$$$ for $$$i > m$$$ or $$$dp(i, 1)$$$

Any help is appreciated, thank you

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English harsh-apcr 2023-11-03 13:00:33 47 Tiny change: 're $S = \{j' \mid s_' -> 're $S = \{ j' \mid s_'
en2 English harsh-apcr 2023-11-03 12:56:53 10
en1 English harsh-apcr 2023-11-03 12:55:37 1064 Initial revision (published)