Doubt in Required Substring CSES problem

#	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

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

Hello everyone, I am trying to solve Required Substring problem from CSES.

First of all, I tried to solve it using combinatorics. My idea was that consider $$$n=6$$$ and string $$$s=$$$ABCDB with 5 characters, then the number of ways we can make $$$n$$$ character string with string $$$s$$$ in it, would be to fix string $$$s$$$ at first position in $$$n$$$ characters and fill rest positions with $$$26$$$ characters, giving $$$numberOfWays = 26$$$. Then, we can shift the substring for $$$(n - m)$$$, i.e, $$$6 - 5 = 1$$$ times to right, and we would get $$$numberOfWays = (n - m + 1) * 26^{(n - m)}$$$, which would, for sample test case, result in $$$numberOfWays = (6 - 5 + 1) * 26^{(6 - 5)} = 52$$$

But, it failed for this test case $$$n=6$$$ and $$$s=$$$ AA. And, I am not able to figure it out, why this is not working because of the large output.

Then, I peeked the solution here, and tried it to code myself, but in the end it is not working. My idea was same as the solution, that is, to build string character by character, and we track progress of building required string as our substring.

My Code

int recurse(int in, int maximumMatchingPrefixLength, int n, int m, int numberOfRequiredSubString) {
    if(in == n) {
        return numberOfRequiredSubString > 0;
    }

    int ans = 0;

    // matching case
    if(maximumMatchingPrefixLength+1 >= m) {
        // insert the last character, and now maximum matching prefix would become 0
        // and number of required substring would increase by 1
        ans += recurse(in+1, 0, n, m, numberOfRequiredSubString+1);
    }
    else {
        // insert that character, which is matching to next character after maximum matching prefix
        // for ex, required substring = ABC
        // and current string is XGAB
        // then, we are inserting C here
        ans += recurse(in+1, maximumMatchingPrefixLength+1, n, m, numberOfRequiredSubString);
    }

    // non matching case
    // insert all those characters, which are coming after any prefix length of Required string
    // and recurse for next position, with that prefix length
    set<char> uc;
    uc.insert(s[maximumMatchingPrefixLength]);
    maximumMatchingPrefixLength = lps[maximumMatchingPrefixLength - 1];
    while(maximumMatchingPrefixLength > 0) {
        uc.insert(s[maximumMatchingPrefixLength]);
        ans += recurse(in+1, lps[maximumMatchingPrefixLength-1], n, m, numberOfRequiredSubString);
        maximumMatchingPrefixLength = lps[maximumMatchingPrefixLength-1];
    }    
    
    // insert other characters, which did not come till now
    ans += (26 - uc.size()) * recurse(in+1, 0, n, m, numberOfRequiredSubString);

    return ans;

}

And, the Solution is following slightly different approach.

Solution

ll solve(int i, int n, int j, string &s)
{
    if(done[i][j]) return dp[i][j];
    done[i][j] = true;
    if(i == n) return dp[i][j] = (j==(int)s.size()?1:0);
    if(j == (int)s.size())
    {
        return dp[i][j] = (mxK*solve(i+1,n,j,s))%mod;
    }
    ll ans = 0;
    int t;
    for(int k = 0; k < mxK; k++)
    {
        t = j;
        while(true)
        {
            if(k == s[t]-'A')
            {
                t++;
                break;
            }
            else if(t)
            {
                t = kmp[t-1];
            }
            else break;
        }
        ans += solve(i+1,n,t,s);
        ans %= mod;
    }
    return dp[i][j] = ans;
}

I think my code is faulty at many places but if someone can tell what mistakes my code is doing, or even the main problem of my code, then it would be really helpful for me.

Thanks

History