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 = \{j' \mid s_1 \ldots s_{j'} \mathrm{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
↵
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 = \{j' \mid s_1 \ldots s_{j'} \mathrm{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
