Standard Digit DP + Knuth-Morris-Pratt
Intuition\nThis is a standard digit DP problem with extra DP state variable used to check if evil substring is present (KMP DFA state). I use DFA version of KMP
# Intuition\nThis is a standard digit DP problem with extra DP state variable used to check if evil substring is present (KMP DFA state). I use DFA version of KMP algorithm because I find it easier to understand and implement (https://www.coursera.org/lecture/algorithms-part2/knuth-morris-pratt-TAtDr).\n\n# Code\n```\nusing ll = long long;\nconst ll MOD = 1e9 + 7;\n\nclass Solution {\npublic:\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        const int ACCEPT_STATE = evil.size();\n        const int ALPHA_SZ = \'z\' - \'a\' + 1;\n        vector<vector<int>> dfa(ACCEPT_STATE, vector<int>(ALPHA_SZ));\n        int shifted_state = 0;\n        dfa[0][evil[0] - \'a\'] = 1;\n        for (int state = 1; state < ACCEPT_STATE; ++state) {\n            dfa[state] = dfa[shifted_state];\n            const char ch = evil[state] - \'a\';\n            dfa[state][ch] = state + 1;\n            shifted_state = dfa[shifted_state][ch];\n        }\n\n        auto count_good = [&](const string& str) -> ll {\n            int memo[n][2][ACCEPT_STATE];\n            memset(memo, -1, sizeof(memo));\n            function<int(int, bool, int)> solve = [&](int idx, bool tight, int dfa_state) -> int {\n                if (idx == n) {\n                    return 1;\n                }\n                int& m = memo[idx][tight][dfa_state];\n                if (m != -1) {\n                    return m;\n                }\n                const char end = tight ? str[idx] - \'a\' : ALPHA_SZ - 1;\n                ll res = 0;\n                for (char ch = 0; ch <= end; ++ch) {\n                    const bool next_tight = tight && ch == end;\n                    const int next_dfa_state = dfa[dfa_state][ch];\n                    if (next_dfa_state != ACCEPT_STATE) {\n                        (res += solve(idx + 1, next_tight, next_dfa_state)) %= MOD;\n                    }\n                }\n                return m = res;\n            };\n            return solve(0, true, 0);\n        };\n        const bool s1_is_good = s1.find(evil) == string::npos;\n        return (MOD + count_good(s2) - count_good(s1) + s1_is_good) % MOD;\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'String Matching', 'C++']