Description：

给以了字符串 $S$ ， $Q$ 次询问，每次给出一个字符串 $T$ 和 $[l,r]$ ，询问是 $T$ 的子串但不是 $S[l,r]$ 的子串的个数。

$1\leqslant |S|,\sum|T|\leqslant 5\times 10^5$

Solution：

先考虑一个部分分： $l=1,r=|S|$ ，这时候的模板串就是整个串，那么我们可以把询问串在模板串上匹配， $i-$ 匹配长度就是所有截止到这个位置的子串对答案的贡献，但是这样显然会算重，于是对询问串建 $SAM$ ，每匹配到一个位置就暴力跳 $par$ ，并标记经过的点，一直到走到根或者走到标记的点位置，计算这些点代表的子串对答案的贡献，实际上就是在某个子串第一次出现时计算贡献。

然后考虑 $l,r$ 任意的情况，我们发现实际用到 $S$ 的地方是计算某个位置和 $S[l:r]$ 的匹配长度，其他地方不用 $S$ ，这个可以用线段树合并维护 $Right$ 集合来解决，并特判几种情况，还有就是匹配的时候要判断这个串是否完整在 $S[l:r]$ 中出现，只有这样才停止跳 $par$ 。

还要注意一个点就是每次查询的时候是查的 $[l+len,r]$ ，但是这个时候如果没有找到我们不能直接跳 $par$ ，因为可能 $len$ 减小一点就能找到了，因此先把 $len-1$ ，因为 $len$ 每次只会加一所以复杂度还是对的。

Code：