Python DP Solution | Using KMP Algorithm | Faster than 77%
\n\n# Code\npython []\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        chars, lenEvil = string.ascii_lowerc
\n\n# Code\n```python []\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        chars, lenEvil = string.ascii_lowercase, len(evil)\n        lps, left = [0] * lenEvil, 0\n        for right in range(1, lenEvil):\n            while left and evil[left] != evil[right]:\n                left = lps[left - 1]\n            if evil[left] == evil[right]:\n                left += 1\n            lps[right] = left\n        \n        @cache\n        def dp(charIdx: int, largerThanS1: bool, smallerThanS2: bool, evilIdx: int) -> int:\n            if charIdx == n:\n                return 1\n            ways = 0\n            for char in chars:\n                if not largerThanS1 and char < s1[charIdx]: continue\n                if not smallerThanS2 and char > s2[charIdx]: continue\n                if evilIdx == lenEvil - 1 and char == evil[evilIdx]: continue\n                if char == evil[evilIdx]:\n                    newEvilIdx = evilIdx + 1\n                else:\n                    newEvilIdx = evilIdx\n                    while newEvilIdx and evil[newEvilIdx] != char:\n                        newEvilIdx = lps[newEvilIdx - 1]\n                    if evil[newEvilIdx] == char:\n                        newEvilIdx += 1\n                ways += dp(charIdx + 1, largerThanS1 | (char > s1[charIdx]), smallerThanS2 | (char < s2[charIdx]), newEvilIdx)\n            return ways % 1000000007\n\n        return dp(0, False, False, 0)\n```
['String', 'Dynamic Programming', 'String Matching', 'Python', 'Python3']