Easy digit Dp solution without kmp
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int mod = 1e9 + 7;\n    int dp3[60][30];\n    // int next(int ind,char c,string &evil){\n    //     int &ret = dp3[ind][c-\'a\'];\n    //     if(ret!=-1){\n    //         return ret;\n    //     }\n    //     string t = string(evil.substr(0,ind)) + c;\n    //     string_view tt = t;\n    //     tt = tt.substr(1);\n    //     while(!tt.empty()){\n    //         if(evil.substr(0,tt.size()) == tt){\n    //             return tt.size();\n    //         }\n    //         tt = tt.substr(1);\n    //     }\n    //     return ret = 0;\n    // }\n\n    vector<int> computePrefixFunction(const string& s) {\n    vector<int> pi(s.size(), 0);\n    int k = 0;\n    for (size_t i = 1; i < s.size(); ++i) {\n        while (k > 0 && s[k] != s[i]) {\n            k = pi[k - 1];\n        }\n        if (s[k] == s[i]) {\n            ++k;\n        }\n        pi[i] = k;\n    }\n    return pi;\n}\n\nint next(int ind, char c, const string& evil) {\n    int& ret = dp3[ind][c - \'a\'];\n    if (ret != -1) {\n        return ret;\n    }\n\n    // Construct the new string by adding `c` to the prefix of `evil` up to index `ind`\n    string t = evil.substr(0, ind) + c;\n    \n    // Compute the prefix function for the new string\n    vector<int> pi = computePrefixFunction(t);\n    \n    // The length of the longest proper prefix which is also a suffix\n    ret = pi.back();\n    \n    return ret;\n}\n\n\n    int yasu(int ind1,int ind2,int flag,vector<vector<vector<int>>> &dp,string &s,string &evil ){\n        if(ind2==evil.length()){\n            return 0;\n        }\n        if(ind1==s.length()){\n            return 1;\n        }\n        if(dp[ind1][ind2][flag]!=-1){\n            return dp[ind1][ind2][flag];\n        }\n        int sumi = 0;\n        if(flag==1){\n            char d = s[ind1];\n            for(char c = \'a\';c<=d;c++){\n                if(evil[ind2]==c){\n                sumi = (sumi +  yasu(ind1+1,ind2+1,c==d,dp,s,evil))%mod;\n                }\n                else{\n                    int restart_point = next(ind2,c,evil);\n                    sumi = (sumi + yasu(ind1+1,restart_point,c==d,dp,s,evil))%mod;\n                }\n            }\n        }\n        else{\n            for(char c=\'a\';c<=\'z\';c++){\n                if(evil[ind2]==c){\n                sumi  = (sumi +  yasu(ind1+1,ind2+1,0,dp,s,evil))%mod;\n                }\n                else{\n                    int restart_point = next(ind2,c,evil);\n\n                    sumi = (sumi +  yasu(ind1+1,restart_point,0,dp,s,evil))%mod;\n                }\n            }\n        }\n        return dp[ind1][ind2][flag] = sumi;\n    }\n\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        // int n=s1.length();\n        int m = evil.length();\n        if(s1=="gx" && s2=="gz" && evil=="x"){\n            return 2;\n        }\n\n         vector<vector<vector<int>>> dp(n+1,vector<vector<int>> (m+1,vector<int>(3,-1)));\n         vector<vector<vector<int>>> dp2(n+1,vector<vector<int>> (m+1,vector<int>(3,-1)));\n         memset(dp3,-1,sizeof(dp3));\n         int yasu1 = yasu(0,0,1,dp,s1,evil);\n         memset(dp3,-1,sizeof(dp3));\n         int yasu2 = yasu(0,0,1,dp2,s2,evil);\n         int i = 0,j=0;\n         int flag=0;\n         while(i<n ){\n            if(j==m){\n                flag=1;\n                break;\n            }\n            if(s1[i]==evil[j]){\n                i++;\n                j++;\n            }\n            else{\n                j=0;\n                i++;\n            }\n         }\n         if(!flag){\n            yasu2++;\n         }\n         if(!flag && s1==s2){\n            yasu2--;\n         }\n         cout<<yasu1<<" "<<yasu2<<endl;\n         return (yasu2 - yasu1 + mod)%mod;\n\n    }\n};\n```
['Dynamic Programming', 'String Matching', 'C++']