2301-替换字符后匹配

给你两个字符串 s 和 sub 。同时给你一个二维字符数组 mappings ，其中 mappings[i] = [oldi, newi]
表示你可以将 sub 中任意数目的 oldi 字符替换为 newi 。sub 中每个字符 不能 被替换超过一次。

如果使用 mappings 替换 0 个或者若干个字符，可以将 sub 变成 s 的一个子字符串，请你返回 true，否则返回
false 。

一个 子字符串 是字符串中连续非空的字符序列。

示例 1：

**输入：** s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]]
**输出：** true
**解释：** 将 sub 中第一个 'e' 用 '3' 替换，将 't' 用 '7' 替换。
现在 sub = "l3e7" ，它是 s 的子字符串，所以我们返回 true 。

示例 2：

**输入：** s = "fooleetbar", sub = "f00l", mappings = [["o","0"]]
**输出：** false
**解释：** 字符串 "f00l" 不是 s 的子串且没有可以进行的修改。
注意我们不能用 'o' 替换 '0' 。

示例 3：

**输入：** s = "Fool33tbaR", sub = "leetd", mappings = [["e","3"],["t","7"],["t","8"],["d","b"],["p","b"]]
**输出：** true
**解释：** 将 sub 里第一个和第二个 'e' 用 '3' 替换，用 'b' 替换 sub 里的 'd' 。
得到 sub = "l33tb" ，它是 s 的子字符串，所以我们返回 true 。

提示：

• 1 <= sub.length <= s.length <= 5000
• 0 <= mappings.length <= 1000
• mappings[i].length == 2
• oldi != newi
• s 和 sub 只包含大写和小写英文字母和数字。
• oldi 和 newi 是大写、小写字母或者是个数字。

如果数据范围再大一点，比如 n=10^5 的话，据我所知就只能用 FFT 做了。大致思路是这样的：令 n=|s|，m=|sub|。对于每种字符 c，定义布尔数组 A[0,\dots,n-1]，其中 A[i]=1 当且仅当 s[i]=c。再定义布尔数组 B[0,\dots,m-1]，其中 B[j]=1 当且仅当 sub[j] 不能变成 c。那么对于任意满足 A[i]=1 的下标 i，以及对于任意满足 B[j]=1 的下标 j，s[i] 不能跟转化后的 sub[j] 匹配上，所以 sub 串的起始位置不能为 i-j。然后用卷积找出所有不合法的起始位置，再对所有字符取 or。总复杂度 O(\sigma\cdot n\log n)，其中 \sigma 为字符集大小。

现在我不理解的是这题为什么被标成了 hard。注意到这场比赛反常地有两个 hard，所以官方标难度的时候应该是考虑过后的有意为之，而且也应该有一个官方算法。好奇以下哪一条出了问题，感觉除了第一条外每条猜测都很离谱：

1. 我智障了，漏掉了什么简单的做法。
2. 官方觉得暴力值得一个 hard。
3. 官方觉得暴力过不了 n=5000。但不被 hard 标签误导的话大家都能看出来这显然能过。
4. 官方做法是这个 FFT。但是 FFT 不应该是大家都熟知的技能。
5. 官方做法是压位 。但是压位也应该不是大家都熟知的技能。
6. 官方算法是错的 kmp。但是测试代码的时候评测后台是可以给出正确的输出的。

也有可能出了不止一个问题。