ningago @ 2022-06-12 13:30:19
RT。匹配时如何特判一个”特殊字符“使得”特殊字符“匹配任何字符都合法。
比如下面的?
T:112?34?33 S:233
____^___^__箭头指的是匹配的位置
by yukimianyan @ 2022-06-12 13:31:24
不跳 fail 直接匹配？
by __qlzxlyc41__ @ 2022-06-12 13:37:24
@ningago 直接过呗
by irris @ 2022-06-12 13:42:16
@qlzxlyc41 那么匹配其他的字符时跳 fail 怎么跳，这货还有多种可能。这个样例太弱了。
by FreshP_0325 @ 2022-06-12 14:08:21
@ningago 不能做
by FreshP_0325 @ 2022-06-12 14:10:12
a?caba?a
这个样例可以自己去手模一下，会发现在处理 nxt[4] 的时候 a 匹配上了一个 c
原因是你直接建转移边之前的位置在动，边的意义不定
并且我怀疑这个东西复杂度也有问题
如果非要做可以看这个 https://www.luogu.com.cn/problem/P4173
by FreshP_0325 @ 2022-06-12 14:12:12
呃，这个东西没法儿构匹配函数，大概是这么个意思吧！
by hly1204 @ 2022-06-12 15:15:15
自动机应该可以，改几个转移边，因为 KMP 算法是基于自动机改造而成的。https://loj.ac/s/952302