C++
KMP + DP \n\n# Complexity\n- Time complexity:\nO(n\xD7e)\n\n- Space complexity:\nO(n\xD7e)\n\n# Code\ncpp []\nclass Solution {\npublic:\n    int mod = 1e9+7;\n 
KMP + DP \n\n# Complexity\n- Time complexity:\nO(n\xD7e)\n\n- Space complexity:\nO(n\xD7e)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int mod = 1e9+7;\n    vector<int> lps;\n    int n, e;\n    string s1, s2, evil;\n    int dp[501][51][2][2];\n\n    vector<int> computeLPS(const string& pattern) {\n        int n = pattern.size();\n        lps.resize(n);\n        lps[0] = 0;\n        int length = 0;\n        int i = 1;\n\n        while (i < n) {\n            if (pattern[i] == pattern[length]) {\n                length++;\n                lps[i] = length;\n                i++;\n            } else {\n                if (length != 0) {\n                    length = lps[length - 1];\n                } else {\n                    lps[i] = 0;\n                    i++;\n                }\n            }\n        }\n        return lps;\n    }\n    int dfs(int i, int e_i, bool isS1Prefix, bool isS2Prefix){\n        if(e_i >= e) return 0;\n        if(i >= n) return 1;\n\n        if(dp[i][e_i][isS1Prefix][isS2Prefix] != -1){\n            return dp[i][e_i][isS1Prefix][isS2Prefix];\n        }\n\n        int start = isS1Prefix ? s1[i]:\'a\';\n        int end = isS2Prefix ? s2[i]:\'z\';\n        int ans = 0;\n        for(char ch=start; ch<=end; ch++){\n            int temp_e_i = e_i;\n            while(temp_e_i > 0 && ch != evil[temp_e_i]){\n                temp_e_i = lps[temp_e_i - 1];\n            }\n            if (ch == evil[temp_e_i]) {\n                temp_e_i += 1;\n            }\n            ans = (ans + dfs(i + 1, temp_e_i, isS1Prefix && ch == start, isS2Prefix && ch == end)) % mod;\n        }\n        return dp[i][e_i][isS1Prefix][isS2Prefix]=ans;\n    }\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        this->lps=computeLPS(evil);\n        this->n=n;\n        this->e=evil.size();\n        this->s1=s1;\n        this->s2=s2;\n        this->evil=evil;\n        memset(dp,-1,sizeof(dp));\n        return dfs(0,0,1,1)%mod;\n    }\n};\n```
['C++']