[C++] No KMP, Digit DP
Intuition\n Describe your first thoughts on how to solve this problem. \nThe KMP table can replaced with next() which has the same functionality as KMP.\n\nInpu
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe KMP table can replaced with ```next()``` which has the same functionality as KMP.\n\nInput the processing ```index of evil``` and the new concatinated ```char c``` we can return the longest prefix of ```evil```.\n\nThe total runtime of this function would be ```O(m * m * m * 26)``` ~ ```3 * 10^6```\n\nThe rest is digit dp: ```O(n * m * 2 * 26)``` ~ ```1.3 * 10^6```\n\nBoth acceptable.\n\n# Code\n```\nclass Solution {\npublic:\n    #define mod 1000000007\n    int dp[501][53][2];\n    string_view s, ev;\n\n    int dp2[51][26];\n\n    int next(int ind, char c) {\n        int &ret = dp2[ind][c - \'a\'];\n        if(ret != -1) return ret;\n        // not found\n        string t = string(ev.substr(0, ind)) + c;\n        string_view tt = t;\n        tt = tt.substr(1);\n        while(!tt.empty()) {\n            if(ev.substr(0, tt.size()) == tt) return ret = tt.size();\n            tt = tt.substr(1);\n        }\n        return ret = 0;\n    }\n\n    int rec(int i, int inde, bool hitight) {\n        if(inde == ev.size()) return 0;\n        if(i >= s.size()) return 1;\n        int &ret = dp[i][inde][hitight];\n        if(ret != -1) return ret;\n        // not found\n\n        long ans = 0;\n\n        for(int a = 0; a < 26; ++a) {\n            char c = a + \'a\';\n            if(hitight && c > s[i]) continue;\n\n            bool nexthi = hitight && c == s[i];\n            if(inde == 0) {  // not start evil yet\n                if(c == ev[inde]) {\n                    ans += rec(i + 1, 1, nexthi);\n                }\n                else {\n                    ans += rec(i + 1, 0, nexthi);\n                }\n            } else { // need to keep evil\n                if(c == ev[inde])\n                    ans += rec(i + 1, inde + 1, nexthi);\n                else {\n                    // ans += rec(i + 1, 0, nexthi);  // should not restart\n                    int restart_point = next(inde, c);\n                    ans += rec(i + 1, restart_point, nexthi);\n                }\n            }\n        }\n        return ret = ans % mod;\n    }\n\n    inline bool alla(string_view s) {\n        for(char c: s) if(c != \'a\')\n            return false;\n        return true;\n    }\n\n    inline bool contains(string_view a, string_view b) {\n        int k = a.size() - b.size() + 1;\n        for(int i = 0; i < k; ++i) {\n            if(a.substr(i, b.size()) == b) return true;\n        }\n        return false;\n    }\n\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        s = s2, ev = evil;\n        memset(dp, -1, sizeof(dp));\n        memset(dp2, -1, sizeof(dp2));\n\n        long LEs2_withoutEV = rec(0, 0, true);\n\n        s = s1, ev = evil;\n        memset(dp, -1, sizeof(dp));\n\n        long LEs1 = rec(0, 0, true);\n\n        return (LEs2_withoutEV - LEs1 + !contains(s1, evil) + mod) % mod;\n    }\n};\n```
['Dynamic Programming', 'C++']