C++ DP solution (with KMP)
\nclass Solution {\n    const int M = 1000000007;\n    void add(int &x, int y) {\n        if ((x += y) >= M) {\n            x -= M;\n        }\n    }\n \npublic
```\nclass Solution {\n    const int M = 1000000007;\n    void add(int &x, int y) {\n        if ((x += y) >= M) {\n            x -= M;\n        }\n    }\n \npublic:\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        const int m = evil.length();\n        vector<int> next(m + 1);\n        next[0] = -1;\n        for (int i = 1; i <= m; ++i) {\n            int j;\n            for (j = next[i - 1]; j >= 0 && evil[i - 1] != evil[j]; j = next[j])\n            ;\n            next[i] = j + 1;\n        }\n        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(4, vector<int>(m)));\n        dp[0][0][0] = 1;\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < 4; ++j) {\n                const int j1 = j >> 1, j2 = j & 1;\n                const char mini = j1 ? \'a\' : s1[i];\n                const char maxi = j2 ? \'z\' : s2[i];\n                for (int k = 0; k < m; ++k) {\n                    if (dp[i][j][k] == 0) continue;\n                    for (char c = mini; c <= maxi; ++c) {\n                        int temp = k;\n                        while (temp > 0 && evil[temp] != c) {\n                            temp = next[temp];\n                        }\n                        const int kk = (evil[temp] == c) ? (temp + 1) : 0;\n                        if (kk < m) {\n                            add(dp[i + 1][((j1 || c > s1[i]) << 1) | (j2 || c < s2[i])][kk], dp[i][j][k]);\n                        }\n                    }\n                }\n            }\n        }\n        int r = 0;\n        for (int j = 0; j < 4; ++j) {\n            for (int k = 0; k < m; ++k) {\n                add(r, dp[n][j][k]);\n            }\n        }\n        return r;\n    }\n};\n```\n\n\nCan be optimized as:\n\n```\nclass Solution {\n    const int M = 1000000007;\n    void add(int &x, int y) {\n        if ((x += y) >= M) {\n            x -= M;\n        }\n    }\n    \n    int get(const string& evil, const vector<int>& next, const int k, const char c,  vector<vector<int>> &have) {\n        int& v = have[k][c - \'a\'];\n        if (v >= 0) return v;\n        if (k > 0  && evil[k] != c) return v = get(evil, next, next[k], c, have);\n        return v = evil[k] == c ? (k + 1) : 0;\n    }\n \npublic:\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        const int m = evil.length();\n        vector<int> next(m + 1);\n        next[0] = -1;\n        for (int i = 1; i <= m; ++i) {\n            int j;\n            for (j = next[i - 1]; j >= 0 && evil[i - 1] != evil[j]; j = next[j])\n            ;\n            next[i] = j + 1;\n        }\n        vector<vector<int>> have(evil.length(), vector<int>(26, -1));\n        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(4, vector<int>(m)));\n        dp[0][0][0] = 1;\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < 4; ++j) {\n                const int j1 = j >> 1, j2 = j & 1;\n                const char mini = j1 ? \'a\' : s1[i];\n                const char maxi = j2 ? \'z\' : s2[i];\n                for (int k = 0; k < m; ++k) {\n                    if (dp[i][j][k] == 0) continue;\n                    for (char c = mini; c <= maxi; ++c) {\n                        const int kk = get(evil, next, k, c, have);\n                        if (kk < m) {\n                            add(dp[i + 1][((j1 || c > s1[i]) << 1) | (j2 || c < s2[i])][kk], dp[i][j][k]);\n                        }\n                    }\n                }\n            }\n        }\n        int r = 0;\n        for (int j = 0; j < 4; ++j) {\n            for (int k = 0; k < m; ++k) {\n                add(r, dp[n][j][k]);\n            }\n        }\n        return r;\n    }\n};\n```
[]