给定串 \(S,T_{1,\cdots,q}\)，每次询问是 \(S[l_i,r_i]\) 的子串但不是 \(T_i\) 的子串的本质不同子串个数。
\(|S|\le5e5,q\le1e5,\sum|T|\le1e6\)。
我们先考虑 \(l=1,r=|S|\) 怎么做。
显然我们使用 SAM 可以简单计算出 \(T_i\) 的本质不同子串数，那么我们肯定想算出来 \(S\) 和 \(T_i\) 的公共子串个数。
我们当然可以把 \(S,T_i\) 拼起来跑 SAM，但是我们想要一个 \(O(\sum T_i)\) 的做法。
可以考虑对 \(T_i\) 的每一个本质不同子串我们都算出来它是否是 \(S\) 的子串，对 \(T_i\) 的每个自动机节点而言，这都是一个前缀，我们只需要算出这个界就可以。而这个界可以通过算出该自动机节点任一 endpos 位置对应的前缀所能匹配上 \(S\) 的最大长度计算出。这个可以在 \(S\) 的自动机上“匹配” \(T_i\) 做到。
现在已经有 \(68\) 分力！
我们考虑加上 \(l,r\) 的限制。我们只需要算出 \(T_i\) 每个前缀能匹配上 \(S[l,r]\) 的最大长度。考虑我们之前的“匹配”过程是怎样的：我们先尝试在最后加入字符 \(T_{i,j}\)，如果加不进去，就不停在前端删除字符（跳 parent 树），直到可加入或跳出为止。
我们发现只需要快速判断能否加入字符 \(T_{i,j}\)，上面的过程是可以照搬的。
现在考虑手头有一个子串 \(S'\)，告诉你对应的 \(S\) 上自动机节点，你要判断它是否在 \([l,r]\) 内。
这个就简单多了！我们只需要知道这个节点内是否存在一个 endpos \(p\)，满足 \(l-|S'|+1\le p\le r\) 即可。
这长得是个二维问题，但我们把询问按 \(r\) 排序，维护 \(p\) 的最大值，每次询问 \([dfnl_x,dfnr_x]\) 内的最大值判断是否 \(\ge l-|S'|+1\) 即可。
总复杂度 \(O(|S|+\sum|T|\log |S|)\)。
标签：子串,前缀,sum,节点,名字,自动机,NOI2018,我们 From： https://www.cnblogs.com/PYD1/p/17472495.html