1397. 找到所有好字符串
题目描述
给你两个长度为 n 的字符串 s1 和 s2 ，以及一个字符串 evil 。请你返回 好字符串 的数目。
好字符串 的定义为：它的长度为 n ，字典序大于等于 s1 ，字典序小于等于 s2 ，且不包含 evil 为子字符串。
由于答案可能很大，请你返回答案对 109 + 7 取余的结果。
示例 1：
输入：n = 2, s1 = "aa", s2 = "da", evil = "b" 输出：51 解释：总共有 25 个以 'a' 开头的好字符串："aa"，"ac"，"ad"，...，"az"。还有 25 个以 'c' 开头的好字符串："ca"，"cc"，"cd"，...，"cz"。最后，还有一个以 'd' 开头的好字符串："da"。
示例 2：
输入：n = 8, s1 = "leetcode", s2 = "leetgoes", evil = "leet" 输出：0 解释：所有字典序大于等于 s1 且小于等于 s2 的字符串都以 evil 字符串 "leet" 开头。所以没有好字符串。
示例 3：
输入：n = 2, s1 = "gx", s2 = "gz", evil = "x" 输出：2
提示：
s1.length == ns2.length == ns1 <= s21 <= n <= 5001 <= evil.length <= 50- 所有字符串都只包含小写英文字母。
解法
方法一
思考
统计长度 \(n\)、字典序落在 \([s_1,s_2]\)、且不含 \(\textit{evil}\) 的串的个数。\(n \le 500\)，枚举全部串不可行。这是带上界的数位 DP：按位填写，同时用 KMP 自动机记录当前已匹配 \(\textit{evil}\) 的前缀长度，一旦到达 \(|\textit{evil}|\) 则非法。对 \(s_2\) 与 \(s_1-1\) 各做一次记忆化，相减取模。
1 | |
1 | |
1 | |
1 | |