1397. Find All Good Strings =========================== 题目信息 -------- :题号: 1397 :难度: Hard :主题: 数位动态规划、字符串、KMP 自动机 :原题: `LeetCode 1397 `_ :重点: 统计长度为 ``n``、字典序位于闭区间 ``[s1,s2]`` 且不含 ``evil`` 连续子串的字符串数量,并取模 题目重述 -------- 给定长度 ``n`` 的两个小写字符串 ``s1``、``s2``,以及小写字符串 ``evil``。好字符串必须长度为 ``n``,字典序不小于 ``s1`` 且不大于 ``s2``,并且不能包含 ``evil`` 作为连续子串。 请返回好字符串数量对 ``10^9 + 7`` 取模后的结果。区间两端都包含在统计中,只要它们自身满足条件。 ``1 <= n <= 500``,``s1.length == s2.length == n``,``1 <= evil.length <= 50``。 自建示例 -------- 排除区间中含禁用字符的字符串: .. code-block:: text 输入:n = 2, s1 = "aa", s2 = "ac", evil = "b" 输出:2 解释:候选为 aa、ab、ac,其中 ab 含有 evil,剩余两个合法。 禁用串比目标长度长时不会出现: .. code-block:: text 输入:n = 1, s1 = "a", s2 = "c", evil = "zz" 输出:3 解释:a、b、c 都不可能包含长度为二的 evil。