题目链接
原题解:
只有一个模式的时候
考虑现在有模式串$M$和文本串$S$,我们想知道是否有$S$的某个子串符合$M$。
先对模式串和文本串进行转化,变成一个整数序列。对于某个字母,如果是在串中第一次出现,那么对应整数$0$;如果不是,则对应到其上一次出现的距离。
比如串$ABBACAB$对应整数序列$0013024$
将$0$看成有一定限制的通配符。
比如在$ABBACAB(0013024)$中查找模式$ABC(000)$.
现在我们可以定义两个整数序列同构的条件。
我们称$M=S$当且仅当对于所有的$i$,以下两条至少有一条满足。
1.$M_i=S_i$
2.$(S_i>i\vee S_i=0) \wedge (M_i>i \vee M_i=0)$
这个$=$具有很重要的传递性。
利用这个全新的相等关系去做KMP就好了,为了利用这个相等关系,你需要知道比较的两个字符串的长度。
多个模式
类似KMP算法,我们可以对整数序列$S$计算$fail$函数。
多个模式的时候利用AC自动机即可。
为了利用那个相等关系,我们需要知道AC自动机上每个节点所对应的串的长度,即对应节点的深度。
补充:
我用暴力过了。字符串题用随机数据就离谱……
代码(100分):
#include
#include
#include
#include
#include
#include
#include
#include