DP || KMP
\nclass Solution {\npublic:\n    \n    /*\n        Hint:\n            1. Run simple dp on [len][evil_match][equal to s1][equal to s2]\n            2. The main t
```\nclass Solution {\npublic:\n    \n    /*\n        Hint:\n            1. Run simple dp on [len][evil_match][equal to s1][equal to s2]\n            2. The main trick or observation is when there is a mismatch!!!\n            3. When a mismatch happens we can\'t just set the [evil_match] to 0 can we?\n            4. No we can\'t we need to look is there are still some prefix match on the string\n            5. And according to that need to find out the new [evil_match]\n            6. We can use kmp/hach for prefix matches.\n        \n        Complexity:\n            Time: O(N * M * 2 * 2 * 26)\n            Space: O(N * M * 2 * 2 * 26)\n    */\n    \n    #define LL long long\n    #define MOD 1000000007\n    LL dp[501][51][2][2];\n    int kmp_mem[51][26];\n    int kmp[51];\n    \n    int get_previous_match(int match, int ch, string &evil) {\n        int &ret = kmp_mem[match][ch - \'a\'];\n        if (ret != -1) return ret;\n        while(match && evil[match] != ch) match = kmp[match - 1];\n        \n        return ret = match + (ch == evil[match]);\n    }\n    \n    LL ans_me(int ix, int match, bool sml, bool big, string &s1, string &s2, string &evil) {\n        if (match == evil.size()) return 0;\n        if (ix == s1.size()) return 1;\n        LL &ret = dp[ix][match][sml][big];\n        if (ret != -1) return ret;\n        ret = 0;\n        \n        int mn = sml ? s1[ix] : \'a\';\n        int mx = big ? s2[ix] : \'z\';\n        for (int i = mn; i <= mx; i++) {\n            ret += ans_me(ix + 1, get_previous_match(match, i, evil), sml && (i == mn), big && (i == mx), s1, s2, evil);\n        }\n        \n        return ret %= MOD; \n    }\n    \n    \n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        memset(dp, -1, sizeof dp);\n        memset(kmp_mem, -1, sizeof kmp_mem);\n        \n        for (int i = 1, cur = 0; i < evil.size(); i++) {\n            while(cur > 0 && evil[cur] != evil[i]) cur = kmp[cur - 1];\n            if (evil[cur] == evil[i]) kmp[i] = ++cur;\n        }\n        \n        return ans_me(0, 0, 1, 1, s1, s2, evil);\n    }\n};\n```
[]