Persistence, Hard Work, Silly Mistake, AC At the end. Refer to comments
Intuition\n Describe your first thoughts on how to solve this problem. \nJust use memoization and KMP Pi table. Enjoy the commentery with the solution. \n\n# Ap
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nJust use memoization and KMP Pi table. Enjoy the commentery with the solution. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long M = 1e9 + 7;\n    int fGS(int i, int j, int z, string &s1, string &s2, string &evil, vector<int>&pi, int &n, int &m, vector<vector<vector<int>>>&dp) {\n        if(j == m - 1)return dp[i][j + 1][z] = 0;\n        if(i == n) return dp[i][j + 1][z] = 1;\n        if(dp[i][j + 1][z] != -1)return dp[i][j + 1][z];\n        /* total strings possible at this position = s2[i] - s1[i] + 1 */\n        /* how many have substring as evil */\n        \n        /* apply KMP for each char */\n        /* lets start : the saviour KMP is here */\n        long long ans = 0;\n        \n        for(char x = ((z & 1) ? s1[i] : \'a\'); x <= ((z & 2) ? s2[i] : \'z\'); x++) {\n            int w = 0;\n            if((z & 1) && (s1[i] == x))w |= 1;\n            if((z & 2) && (s2[i] == x))w |= 2;\n            if(x == evil[j + 1])ans += fGS(i + 1, j + 1, w, s1, s2, evil, pi, n, m, dp);\n            else {\n                int k = j;\n                while(k != -1 && evil[k + 1] != x) {\n                    k = pi[k];\n                }\n                /* mistake I did cost me 3 hours of time */\n                if(evil[k + 1] == x)ans += fGS(i + 1, k + 1, w, s1, s2, evil, pi, n, m, dp);\n                else ans += fGS(i + 1, k, w, s1, s2, evil, pi, n, m, dp);\n            }\n            ans %= M;\n        }\n        return dp[i][j + 1][z] = ans;\n        // have to use both logics at once \n    }\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        vector<int>pi(evil.size(), -1);\n\n        /* construct pi table */\n        int i = 1, j = -1;\n        // int n = s1.size();\n        int m = evil.size();\n        while(i < m) {\n            if(evil[j + 1] == evil[i])pi[i] = j + 1, j++, i++;\n            else if(j != -1)j = pi[j];\n            else i++;\n        }\n\n        /* done */\n        /* call recursion */\n        vector<vector<vector<int>>>dp(n + 1, vector<vector<int>>(m + 1, vector<int>(4, -1)));\n        return fGS(0, -1, 3, s1, s2, evil, pi, n, m, dp);\n    }\n};\n```
['C++']