给定字符串 \(S\)，令 \(s(S)\) 表示 \(S\) 的所有子串构成的集合，有 \(Q\) 个询问，每次给一个字符串 \(T\) 和两个正整数 \([l,r]\)，询问 \(|s(T)-s(S[l:r])|\)。
数据范围：\(|S|\le 5\times 10^5, Q\le 10^5, \sum |T|\le 10^6\)。
我们考虑固定 \(T\) 的子串的左端点为 \(i\)，询问多少子串不在 \(S\) 中，那么我们只需要找到最大的 \(j\) 使得 \(T[i:j]\) 仍然在 \(S\) 中，也就是 \(i\) 往右扩展了多少，我们先将这个 \(j\) 命名为 \(f_i\)。假设我们已经求出了 \(\{f_i\}\)，接下来考虑 \(T\) 的后缀树，如果对于每个 \(T[i:f_i]\) 都走一遍后缀树把经过的点标记上，那么我们要问的就是未被标记的点的个数。
现在我们需要求出 \(\{f_i\}\)，先考虑 \(l=1,r=n\) 的做法，我们先求 \(f_1\)，这可以在后缀树上往下搜。接下来考虑 \(f_2\) 如何求，我们只需要跳到 \(f_1\) 所处节点的后缀链接上，然后继续往下搜。由于右端点一直在往右走，所以时间复杂度是线性。
现在考虑 \(l,r\) 不固定，假设此时我们已经扩展的长度为 \(len\) ，那么这个子串在 \(S\) 中的左端点的位置是 \([l,r-len+1]\)。所以在后缀树上搜索时，我们需要格外关注所在节点的子树的叶子中是否有叶子代表的后缀编号在 \([l,r-len+1]\) 中，这样才能确保我们的字符串是在 \(S[l:r]\) 中出现而不是在别的地方。
现在我们使用数据结构维护这个事情，我们使用可持久化线段树合并得到每个点的子树中的叶子代表的后缀编号的集合，也就是一个 01 串。时间复杂度 \(O(n\log n)\)。
咕了
原文：https://www.cnblogs.com/wyy603/p/12907450.html