给出字符串 \(s\) 以及 \(q\) 个询问，第 \(i\) 个询问给出一个串 \(t_i\) 以及一个区间 \([l_i,r_i]\)。
记 \(s[l,r]\) 为字符串 \(s\) 第 \(l\) 位到第 \(r\) 位字符顺次拼接而成的子串。形式化地，\(s[l,r]=\overline{s_ls_{l+1}\dots s_r}\)。
对于每个询问，求 \(t_i\) 有多少种本质不同的子串没有在 \(s[l_i,r_i]\) 中出现。
\(|s|\le 5\times 10^5,q\le 10^5,\sum\limits_{i=1}^q|t_i|\le 10^6\)。
\(\text{5.00 s / 768.00 MB}\)。
神仙字符串题。
首先把所有字符串用特殊字符接起来，得到一个大串 \(S\)。对 \(S\) 进行后缀排序。这样不改变任意两个后缀的 \(\text{LCP}\)。
对于每一组询问，考虑容斥，即用 \(t_i\) 中的本质不同子串个数减去在 \(s[l_i,r_i]\) 中出现过的。
前半部分是平凡的，即按排名考虑每一个后缀带来的本质不同子串个数，根据经典结论就是这个后缀的前缀数减去它的 \(\text{height}\)。
至于后半部分，同样这样考虑每个后缀带来的本质不同子串中有多少个在 \(s[l_i,r_i]\) 中出现。我们发现若一个后缀 \(\boldsymbol{t_i[j,e]}\) 在 \(\boldsymbol{s[l_i,r_i]}\) 中出现，则 \(\boldsymbol{t_i[j,e-1]}\) 也在 \(\boldsymbol{s[l_i,r_i]}\) 中出现。所以可以考虑二分这个最大的结束位置 \(e\)。判断 \(t_i[j,e]\) 是否在 \(s[l_i,r_i]\) 中出现就是判断是否存在一个位置 \(k\) 使得 \(k\in[l_i,r_i-e+j]\) 且 \(|\text{LCP}(S[k,|S|],t_i[j,e])|\ge e-j+1\)。
二分出排名区间，主席树二维数点检查即可。得到这个值后，\(t_i[j,j+\text{height}_j]\sim t_i[j,e]\) 这些本质不同子串在 \(s[l_i,r_i]\) 中出现，直接减去个数即可。
但是这样回答单组询问的时间复杂度为 \(\mathcal{O}(|t_i| \log |S|\log |t_i|)\)，无法接受。
思考一下二分的目的，我们想要对于 \(t_i\) 的每个后缀，得到一个最大的长度 \(L_j\)，使得 \(t_i[j,j+L_j-1]\) 在 \(s[l_i,r_i]\) 中出现。
我们发现一个关键性质，那就是 \(\boldsymbol{L_j\ge L_{j-1}-1}\)。因为这两个后缀只差了开头的这一位。
我们可以类似于 \(\text{height}\) 数组那样，用一个指针 \(k\) 表示当前 \(t_i[j,j+k-1]\) 在 \(s[l_i,r_i]\) 中出现，检查是否可行时仍然二分排名区间 + 主席树。若可行则 \(k\) 右移。
由于最多递减 \(\mathcal{O}(|t_i|)\)，因此 \(k\) 最多移动 \(\mathcal{O}(|t_i|)\) 次，这样单组询问的时间复杂度就是 \(\mathcal{O}(|t_i|\log |S|)\)。
综上，我们得到了一个时间、空间复杂度均为 \(\mathcal{O}(|S|\log |S|)\) 的做法。
提交记录（\(\color{limegreen}\bf Accepted\space100\)，\(\bf{4.62\, s / 606.29\, MB}\)） 代码
标签：子串,boldsymbol,log,记录,后缀,text,P4770,mathcal,NOI2018 From： https://www.cnblogs.com/MnZnOIerLzy/p/17870822.html