题意

给定一个文本串$s$，若干询问，每次询问给定一个区间$[l,r]$和一个模式串$t$，求 $t$ 中不存在于$s_l...s_r$的字串个数。

$|s| \leq 10^6 , \sum|t|\leq 10^6,q \leq 10^5$

Solution

写三次SAM挂三次，全体目光向我看齐：我宣布个事! 我是个小可爱

先对$s$建立一个SAM

Case1 : $l=1,r=|s|$

全局情况，我们计算 $t$ 每一个前缀的贡献，具体地说，我们求一个$f_i$表示 $t_{1...i}$和$s$匹配的最大后缀长度(同类型题目SPOJ-LCS)，这样对于每一个$i$，$t$上合法的串只存在于$[1...i-f_i,i]$中。

现在对$t$单独建立一个SAM，对于每一个非根节点，都对应一个等价类，每一个等价类的贡献为

$ans=\max(0,\operatorname{len_i} -\max(\operatorname{len_{link_i}},f_{\operatorname{id_i}}))$

其中$\operatorname{id_i}$表示这个等价类的最小位置，具体的，$\operatorname{id_i}$为每次新建节点$p$时的$\operatorname{len_{last}}+1$，在clone操作时直接复制。

复杂度$O(|s|+\sum|t|)$

Case2 :

现在加上区间限制。

首先发现区间限制仅影响对$f_i$的求解，其余情况是不变的，它影响到是否将当前状态$(p,l)$更新。

现给$\operatorname{SAM_s}$上标记$id$，$id_i$表示$s_i$对应的状态，同时在parent tree上跑dfs序。

假设现在状态处理到$(p,l)$，向$c$转移，如果状态$p$中存在一个向$c$的转移，且$l\leq id-l-1 \leq r$，那么就可以转移，同时根据parent tree的性质：根一定是子树节点的后缀，故若根有向$c$的转移，子树节点也会有向$c$的转移，倘若询问的$r$非降，那么$id$越大，则$id-l-1$越大，所以维护子树最大值即可。

具体根据parent tree的dfn序建立线段树查询区间最大值。

所以对所有询问按照$r$排序，维护最大值。

tips

但如果你真的按照例题的写法(指直接跳$\operatorname{link}$)，可能会得$94 pts$(数据真水)，为什么捏？

考虑判断转移是否可行的条件，为

1. 有向$c$的转移
2. 最大值满足在区间内

如果条件1满足但条件2不满足，倘若直接跳$\operatorname{link}$，就会漏解

正确的做法是不断将$l-1$，直至$l=\operatorname{link_p}$，这时再跳$\operatorname{link}$