Digit DP + Z-Function || Easy to understand || Beats 100% || C++
Complexity\n- Time complexity:O(n * m^2 * 26)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity:O(n * m * 2)\n Add your space complexity here, e
# Complexity\n- Time complexity:$$O(n * m^2 * 26)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n * m * 2)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nint dp[505][2][55];\nclass Solution {\npublic:\n    vector<int> zFunction(string& s){\n        int n = s.size();\n        vector<int> z(n, 0);\n        int l = 0, r = 0;\n        for(int i=1; i<n; i++){\n            if(i <= r) z[i] = min(r - i + 1, z[i-l]);\n            while(s[z[i]] == s[i+z[i]]) z[i]++;\n            if(i + z[i] - 1 > r){\n                l = i;\n                r = i + z[i] - 1;\n            }\n        }\n        z[0] = n;\n        return z;\n    }\n    int mod = 1e9 + 7;\n    int solve(int i, int n, int tight, int match, string& s, string& e, vector<int>& z){\n        if(match == size(e)) return 0;\n        if(i == n) return 1;\n        if(dp[i][tight][match] != -1) return dp[i][tight][match];\n        char ub = tight ? s[i] : \'z\';\n        int ans = 0;\n        for(char c = \'a\'; c <= ub; c++){\n            bool fg = true;\n            for(int j=0; j<min(match, n); j++){\n                int len = match - j;\n                if(z[j] >= len && e[len] == c){\n                    ans = (ans + solve(i+1, n, tight & (c == ub), len + 1, s, e, z)) % mod;\n                    fg = false;\n                    break;\n                }\n            }\n            if(fg) ans = (ans + solve(i+1, n, tight & (c == ub), c == e[0], s, e, z)) % mod;\n        }\n        return dp[i][tight][match] = ans;\n    }\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        vector<int> z = zFunction(evil);\n        memset(dp, -1, sizeof dp);\n        int r = solve(0, n, 1, 0, s2, evil, z);\n        memset(dp, -1, sizeof dp);\n        int l = solve(0, n, 1, 0, s1, evil, z);\n        if(s1.find(evil) == string::npos) r++;\n        return (r - l + mod) % mod;\n    }\n};\n```
['C++']