C++ Dynamic Programming (Digit DP) + KMP (60ms)
Use the strategy of Dynamic Programming (Digit DP) & KMP Algorithm\n\nyou can find the detail description of digit dp at this page https://www.***.org/digit-dp-
Use the strategy of Dynamic Programming (Digit DP) & KMP Algorithm\n\nyou can find the detail description of `digit dp` at this page https://www.***.org/digit-dp-introduction/\n\nIt\'s just a template\n\n```cpp\nconst int MAX = 505;\nconst int MOD = 1e9+7;\n\nclass Solution {\npublic:\n    long long dp[MAX][2][MAX];\n    int digestArr[MAX], digestLen = 0;\n\n    long long dfs(int length, int isSmall, int state) {\n        if (state == evil.size()) {\n            return 0;\n        }\n\n        if (length == 0) {\n            return 1;\n        }\n\n        if (dp[length][isSmall][state] != -1) {\n            return dp[length][isSmall][state];\n        }\n\n        long long answer = 0;\n        for (int i = 0; i <= 25; i++) {\n            if (!isSmall && i > digestArr[length]) {\n                break;\n            }\n\n            if (i == evil[state] - \'a\') {\n                answer += dfs(\n                        length - 1,\n                        isSmall || i < digestArr[length],\n                        state + 1\n                );\n            } else {\n                int j = state;\n\n                while (j > 0 && i != evil[j] - \'a\') {\n                    j = nxt[j];\n                }\n\n                if (j == -1 || evil[j] - \'a\' == i) {\n                    j++;\n                }\n\n                answer += dfs(\n                        length - 1,\n                        isSmall || i < digestArr[length],\n                        j\n                );\n            }\n\n            answer %= MOD;\n        }\n\n        return dp[length][isSmall][state] = answer;\n    }\n\n    long long solve(const string& s) {\n        std::memset(dp, 0xff, sizeof(dp));\n        std::memset(digestArr, 0, sizeof(digestArr));\n\n        const int N = s.size();\n        digestLen = 0;\n        for (int i = N - 1; i >= 0; i--) {\n            digestArr[++digestLen] = s[i] - \'a\';\n        }\n\n        return dfs(digestLen, 0, 0);\n    }\n\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        if (s1 > s2) return 0;\n\n        this->evil = evil;\n        buildkmp();\n\n        long long answer2 = solve(s2);\n        long long answer1 = solve(s1);\n\n        long long tmp = (((answer2 - answer1) % MOD) + MOD) % MOD;\n        if (s1.find(evil) == string::npos) tmp++;\n        tmp %= MOD;\n\n        return tmp;\n    }\nprivate:\n    string evil;\n    vector<int> nxt;\n    void buildkmp() {\n        const string& s = evil;\n\n        const int N = s.size();\n        nxt = vector<int>(N + 1, 0);\n        nxt[0] = -1, nxt[1] = 0;\n\n        int i = 1, j = 0;\n        while (i < N) {\n            if (j == -1 || s[i] == s[j]) {\n                nxt[++i] = ++j;\n            } else {\n                j = nxt[j];\n            }\n        }\n    }\n};\n```
[]