3679.组合技
2026-10-14
题解
既然有多个模式串,考虑先建出 AC 自动机,容易发现,在 t 在上面走的时候,其 Fail 树上的祖先都出现了,也就是说一个模式串是另一个模式串的子串是无用的。
此时我们只需要保留所有 Fail 树上的叶子节点,考虑对 r 扫描线应该怎么计数。
观察到 r 增大时 l 不降,那么维护每个位置到 r 的模式串个数即可,设 cnt[i] 表示从 i 到 r 出现的所有模式串个数,初始时 cnt[0]=n−m(即叶子节点数量)。
那么有一个天才的想法:直接初始时让 l=0,然后当 cnt[l]=0 时令 l←l+1(l=0 时 cnt=0 代表所有模式串已经出现过,以此类推),这样只需要 ans←ans+l 即可。
