Python Digit DP + KMP (Pattern For Similar Questions)
Theory: https://codeforces.com/blog/entry/53960\n\nMore of the same approach:\n902. Numbers At Most N Given Digit Set\n788. Rotated Digits\n1012. Numbers With R
Theory: https://codeforces.com/blog/entry/53960\n\nMore of the same approach:\n[902. Numbers At Most N Given Digit Set](https://leetcode.com/problems/numbers-at-most-n-given-digit-set/discuss/559624/python-digit-dp)\n[788. Rotated Digits](https://leetcode.com/problems/rotated-digits/discuss/560601/python-digit-dp)\n[1012. Numbers With Repeated Digits](https://leetcode.com/problems/numbers-with-repeated-digits/discuss/560346/python-digit-dp)\n[357. Count Numbers with Unique Digits](https://leetcode.com/problems/count-numbers-with-unique-digits/discuss/560898/Python-Digit-DP)\n[233. Number of Digit One](https://leetcode.com/problems/number-of-digit-one/discuss/560876/Python-Digit-DP)\n[600. Non-negative Integers without Consecutive Ones](https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/discuss/584350/Python-Digit-DP-(Pattern-For-Similar-Questions))\n\nAt each recursive call (adding letter to less significant position) compute:\n\nprefS1 - if the new number is the prefix of s1\nprefS2 -  if the new number is the prefix of s2\nevilLen - length of matching of the current number with evil string\nUse KMP to compute the new matching with evil string.\n\n```\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        kmp = self._kmp(evil)\n\n        @functools.lru_cache(None)\n        def dp(i, prefS1, prefS2, evilLen):\n            if evilLen == len(evil):\n                return 0\n            if i == n:\n                return 1\n            first = s1[i] if prefS1 else \'a\'\n            last = s2[i] if prefS2 else \'z\'\n            result = 0\n            for ci in range(ord(first), ord(last) + 1):\n                c = chr(ci)\n                _prefS1 = prefS1 and s1[i] == c\n                _prefS2 = prefS2 and s2[i] == c\n\n                j = evilLen\n                while j and evil[j] != c:\n                    j = kmp[j - 1]\n                if evil[j] == c:\n                    j += 1\n\n                result += dp(i + 1, _prefS1, _prefS2, j)\n            return result % (10 ** 9 + 7)\n\n        return dp(0, True, True, 0)\n    \n    def _kmp(self, pattern: str):\n        tab = [0] * len(pattern)\n        j = 0\n        for i in range(1, len(pattern)):\n            while j and pattern[i] != pattern[j]:\n                j = tab[j - 1]\n            if pattern[i] == pattern[j]:\n                j += 1\n            tab[i] = j\n        return tab\n```
[]