找到所有好字符串

这道题的解法使用了动态规划和KMP算法的思想。首先通过KMP算法的前缀函数计算出evil字符串的前缀函数，然后基于前缀函数构建一个dp数组，dp[i][j]表示evil字符串的前i个字符与某个字符串匹配，且当前匹配到字符j时，evil字符串的最大匹配长度。接下来使用记忆化搜索，枚举满足条件的字符串，搜索过程中维护当前枚举到的位置i，当前匹配的evil字符串的长度match，以及是否受到s1和s2的字典序限制。搜索到字符串末尾时，如果match小于evil字符串的长度，说明当前字符串是好字符串，累加答案。

时间复杂度: O(n × m × 26)

空间复杂度: O(n × m + m × 26)

class Solution:
    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
        def prefix_function(pattern: str) -> []:
            # 计算字符串pattern的前缀函数
            n = len(pattern)
            pi = [0] * n
            for i in range(1, n):
                j = pi[i - 1]
                while j != 0 and pattern[i] != pattern[j]:
                    j = pi[j - 1]
                if pattern[i] == pattern[j]:
                    j += 1
                pi[i] = j
            return pi

        def match_char(pattern: str) -> []:
            # 构建dp数组，dp[i][j]表示pattern的前i个字符与某个字符串匹配，且当前匹配到字符j时，pattern的最大匹配长度
            n = len(pattern)
            pi = prefix_function(pattern)
            dp = [[0 for j in range(26)] for i in range(n)]
            dp[0][ord(pattern[0]) - 97] = 1
            for i in range(1, n):
                for cur in range(0, 26):
                    ch = chr(cur + 97)
                    if ch == pattern[i]:
                        dp[i][cur] = i + 1
                    else:
                        j = pi[i - 1]
                        dp[i][cur] = dp[j][cur]
            return dp

        n = len(s2)
        pn = len(evil)
        dp = match_char(evil)

        @lru_cache(None)
        def dfs(i:int, match:int, limit_low:bool, limit_high:bool) -> int:
            # 记忆化搜索，枚举满足条件的字符串
            if i == n:
                return match < pn
            if match >= pn:
                return 0
            lo = ord(s1[i]) if limit_low else ord('a')
            hi = ord(s2[i]) if limit_high else ord('z')
            res = 0
            for cur in range(lo, hi + 1):
                res += dfs(i+1, dp[match][cur - 97], limit_low and cur == lo, limit_high and cur == hi)
            res %= (10 ** 9 + 7)
            return res
        return dfs(0, 0, True, True)