题解

未分类

答案可以分为两部分，在字典串中出现的和在字典串之间出现的，前者容易计算，对于后者，我们考虑出现位置中第一个标号序列中的位置是 $i$ ，枚举 $i$ ，查询 $\sum_{i=1}^{n-1} c(t, s[\max(lp_i, rp_i-|t|+1):rp_i+|t|-1])$ 即可，其中 $c(t,s)$ 表示 $t$ 在 $s$ 中的出现次数

Part 1. $O(m\log n)-O(n\log n)$

定义 $\tau(s, t) = \mathrm{suf}(s)\cup \mathrm{pre}(t)$ 。
定理：令 $\tau(s,t) = \{ s[p_i:] \}$ ，其中 $p$ 是一个单调不降的序列，则 $p$ 可以被表示成 $O(\log n)$ 个等差数列顺次连接起来。
Proof. $s[p_{i+1}:]$ 是 $s[p_i:]$ 的前缀，因此只有两种情形：
1. $|s[p_{i+1}:]|\leqslant |s[p_i:]|/2$ ：长度 /2 ，不需要处理
2. $|s[p_{i+1}:]|>|s[p_i:]|/2$ ：必然会出 period ，我们可以把形如 $p_k=p_i+(k-i)l$ 的位置压成一个等差数列，其中 $l$ 是 period 长度。则处理后的 $|s[p_j:]|<|s[p_i:]|/2$ ，其中 $j>i$ 是第一个不在等差数列里的下标。
得证。

于是问题来到怎么求 $\tau(s,t)$ ，容易在 $O(\log n)$ 的时间内求出 $\max\{\mathrm{LCP}(s[i:],t) | i\in[l,r] \}$ ，注意到如果 $s[l:]\in\tau(s,t)$ 则必然 $\max\{\mathrm{LCP}(s[i:],t) | i\in[l,r] \}=s[l:]$ ，于是我们就可以在 $O(\log n)$ 的时间内由 $p_i$ 求出 $p_{i+1}$ （以及求出 $p_1$ ），而注意到在等差数列里我们只要知道第一项和第二项的位置就可以求出整个等差数列。因此我们就可以在 $O(\log^2 n)$ 的时间内求出 $\tau(s,t)$ 。注意到其实我们只需要求出 $p_1$ ，因为序列的其余部分是可以预处理后直接用 $p_1$ 回答出来的。于是就可以用 $O(\log n)$ 的时间内求出来。

我们要求 $c(t, s[\max(lp_i, rp_i-|t|+1):rp_i+|t|-1])$ ，把串分为 $ls=s[\max(lp_i, rp_i-|t|+1):rp_i]$ 和 $rs=s[rp_i:rp_i+|t|-1]$ ，我们就是要求 $\tau(ls,t)$ 和 $\tau(t,rs)$ ，然后把两部分结果合并起来（求 $|\tau(ls,t)\cup\{p-|t| |p\in \tau(t,rs)\}|$），这个可以把两部分归并起来计算贡献即可。复杂度 $O(\log n)$ 。

Part 2. $O(nL)-O(\sqrt{n})$ (offline) / $O(nL\log n)-O(\log n)$ (online)

我们要查询 $\sum_{i=1}^{n-1} c(t, s[\max(lp_i, rp_i-|t|+1):rp_i+|t|-1])$ 。在考虑 $s[\max(lp_i, rp_i-L+1):rp_i+L-1]$ 这个串的贡献的时候，我们把 $s[k:]$ 这个后缀标号为 $|k-rp_i|$ ，而要查询的和就是查询在整个 Trie 上 SAM 的对应节点的子树里有多少后缀节点的标号 $<|t|$ ，考虑这就是一个二维数点， $O(nL)$ 个点，如果离线的话还是可以做到 $O(nL)$ 预处理 $O(\sqrt{n})$ 回答，如果在线的话可能就要变成 $O(nL\log n)-O(\log n)$ 了。

综上，取 $L=\sqrt{n\log n}$ ，复杂度为 $O(m\log n+n\sqrt{n\log n}+q\sqrt{n})$ (Offline)