C++/Rust Digit DP + KMP Solution
Intuition\nDP + KMP\n\n# Complexity\n- Time complexity: O(n * evil)\n\n- Space complexity: O(n * evil) \n\n# Code\nC++ []\nconst int mod = 1e9+7;\nclass Solutio
# Intuition\nDP + KMP\n\n# Complexity\n- Time complexity: O(n * evil)\n\n- Space complexity: O(n * evil) \n\n# Code\n```C++ []\nconst int mod = 1e9+7;\nclass Solution {\n    long long dp[501][51][2][2]={};\npublic:\n    Solution(){\n        ios::sync_with_stdio(false);\n        cin.tie(nullptr);\n    }\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        return dfs(0, 0, true, true, n, s1, s2, evil, kmpArray(evil));\n    }\nprivate:\n    int dfs(int pos, int evilMatched, bool boundLower, bool boundUpper, const int& n, const string& s1, const string& s2, const string& evil, const vector<int>& kmp){\n        if(evilMatched == evil.size())\n            return 0;\n        if(pos == n)\n            return 1;\n        if(dp[pos][evilMatched][boundLower][boundUpper])\n            return dp[pos][evilMatched][boundLower][boundUpper];\n        \n        char lo = boundLower ? s1[pos] : \'a\';\n        char hi = boundUpper ? s2[pos] : \'z\';\n        \n        long long ans=0;\n        for(char c=lo; c<=hi; ++c){\n            int j = evilMatched;\n            while(j && evil[j] != c)\n                j = kmp[j-1];\n            if(evil[j] == c)\n                ++j;\n            ans += dfs(pos+1, j, boundLower && (c == lo), boundUpper && (c == hi), n, s1, s2, evil, kmp);\n            ans %= mod;\n        }\n        return dp[pos][evilMatched][boundLower][boundUpper] = ans;\n    }\n    vector<int> kmpArray(const string& evil){\n        int i=1, len=0;\n        const int n = evil.size();\n        vector<int> kmp(n);\n        \n        while(i < n){\n            if(evil[i] == evil[len])\n                kmp[i++] = ++len;\n            else{\n                if(len)\n                    len = kmp[len-1];\n                else\n                    ++i;\n            }\n        }\n        return kmp;\n    }\n};\n```\n```Rust []\nuse std::cmp::Ordering;\nstatic MOD: i64 = 1_000_000_007;\nimpl Solution {\n    pub fn find_good_strings(n: i32, s1: String, s2: String, evil: String) -> i32 {\n        let evil = evil.as_bytes();\n        let evil_len = evil.len();\n        fn kmp(evil: &[u8], n: usize) -> Vec<usize>{\n            let (mut i, mut len) = (1, 0);\n            let mut dp = vec![0; n];\n            while i < n{    \n                if evil[i].cmp(&evil[len]) == Ordering::Equal{\n                    len += 1;\n                    dp[i] = len;\n                    i += 1;\n                } else{\n                    match len > 0{\n                        true => {len = dp[len - 1];},\n                        _ => {i += 1;}\n                    }\n                }\n            }\n            dp\n        }\n        let kmp_array = kmp(evil, evil_len);\n\n        fn dfs(pos: usize, evil_matched: usize, lower_bound: bool, upper_bound: bool, \n                n: usize, s1: &[u8], s2: &[u8], evil: &[u8], kmp: &Vec<usize>, \n                dp: &mut Vec<Vec<Vec<Vec<i64>>>>) -> i64{\n            if evil_matched == evil.len(){\n                return 0;\n            }\n\n            if pos == n{\n                return 1;\n            }\n\n            if dp[pos][evil_matched][lower_bound as usize][upper_bound as usize] != -1{\n                return dp[pos][evil_matched][lower_bound as usize][upper_bound as usize];\n            }\n\n            let lo = if lower_bound {s1[pos]} else {b\'a\'};\n            let hi = if upper_bound {s2[pos]} else {b\'z\'};\n            let mut ans = 0;\n            for c in lo..=hi{\n                let mut j = evil_matched;\n                while j > 0 && evil[j] != c{\n                    j = kmp[j - 1];\n                }\n                if evil[j] == c{\n                    j += 1;\n                }\n\n                ans += dfs(pos + 1, j, (c== lo) & lower_bound, upper_bound & (c == hi), n, s1, s2, evil, kmp, dp);\n                ans %= MOD;\n            }\n            dp[pos][evil_matched][lower_bound as usize][upper_bound as usize] = ans;\n            ans\n        }  \n\n        let mut dp = vec![vec![vec![vec![-1; 2]; 2]; evil_len]; n as usize];\n        dfs(0, 0, true, true, n as usize, s1.as_bytes(), \n            s2.as_bytes(), evil, &kmp_array, &mut dp) as i32 \n    }\n}\n```
['C++', 'Rust']