O(N * len(evil)) Solution with memorized DP & KMP algorithm
py\ndef getKmpNext(pattern):\n    """ get KMP next arrray\n    \n    next[i] is the biggest k s.t. pattern[:k] == pattern[:i + 1][-k:]\n    """\n    nextArr = [
```py\ndef getKmpNext(pattern):\n    """ get KMP next arrray\n    \n    next[i] is the biggest k s.t. pattern[:k] == pattern[:i + 1][-k:]\n    """\n    nextArr = [0] * len(pattern)\n    i, j = 1, 0\n    while i < len(pattern):\n        while j and pattern[j] != pattern[i]:\n            j = nextArr[j - 1]\n        if pattern[i] == pattern[j]:\n            j += 1\n        nextArr[i] = j\n        i += 1\n    return nextArr\n\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        from functools import lru_cache\n        \n        m = len(evil)\n        mod = int(1E9 + 7)\n        nextArr = getKmpNext(evil)\n        \n        @lru_cache(None)\n        def cnt(idx, pre1, pre2, preE):\n            """\n            we try to build target string each char.\n            \n            the basic idea is that we can get the count of valid string which begin with a special prefix.\n            but if we use the prefix as a parameter, the DP space will be too big.\n            so we just extract three params from the prefix: if it\'s prefix of s1 or s2 or evil.\n            \n            idx(int) is the index char of target to build.\n            \n            pre1(bool) means if the prefix of current position is a prefix of s1.\n                if it is, the char we put here cannot less than s1[idx].\n            \n            pre2(bool) means if the prefix of current position is a prefix of s2.\n                if it is, the char we put here cannot greater than s2[idx].\n                \n            preE(int) is the max length of commom prefix between current position and evil.\n                if it is len(evil), we cannot build any string begin with current prefix.\n                we use KMP algorithm to calculate it.\n            """\n            if preE == m: return 0\n            if idx == n: return 1\n            \n            total = 0\n            first = ord(s1[idx]) if pre1 else ord(\'a\')\n            last = ord(s2[idx]) if pre2 else ord(\'z\')\n            \n            for ci in range(first, last + 1):\n                c = chr(ci)\n                \n                _pre1 = pre1 and ci == first\n                _pre2 = pre2 and ci == last\n\n                # using KMP to calculate _preE\n                _preE = preE\n                while _preE and c != evil[_preE]:\n                    _preE = nextArr[_preE - 1]\n                if c == evil[_preE]:\n                    _preE += 1\n\n                total += cnt(idx + 1, _pre1, _pre2, _preE)\n                total %= mod\n            \n            return total\n        \n        return cnt(0, True, True, 0);\n```
[]