[OOI 2023] 字符串问题

我们记 $count(h)$ 为字符串 $h$ 的所有子串中，出现在集合 $S$ 里的子串数量。对于每个询问，我们需要计算 $count(h[l_i, r_i])$。令 $pref[i] = count(t[0:i))$，即 $t$ 的长度为 $i$ 的前缀中，出现在 $S$ 中的子串数量。令 $suf[i] = count(t[i:|t|))$，即从位置 $i$ 开始的后缀在 $S$ 中出现的子串数量。

可以发现，$pref[r] + suf[l] - count(t)$ 等于 $count(t[l, r])$，再减去那些属于 $S$ 的子串，这些子串在 $t$ 中的起点早于 $l$，终点晚于 $r$。如果不存在这种“跨界”子串，那么答案就很容易求出，所有需要的 $pref[l]$ 和 $suf[r]$ 都可以通过 Aho-Corasick 算法计算得到。

如果存在上述“跨界”子串，则对于询问 $t[l, r]$，我们需要找到这样一个 $S$ 中的子串 $s_i$，它在 $t$ 中的出现起点早于 $l$，终点晚于 $r$。在所有满足条件的 $s_i$ 中，选择右端点最靠左的那个。设其为 $s_i$。注意，$t[l, r]$ 是 $s_i$ 的一个子串，记作 $s_i[l', r']$。同时，$s_i$ 中不存在起点早于 $l'$、终点晚于 $r'$且属于 $S$ 的子串（否则 $t[l, r]$ 会被更靠右的 $S$ 中子串覆盖）。因此，我们可以对 $s_i$ 应用前缀和后缀的原理，递归求解。

为了在询问 $t[l, r]$ 时找到合适的 $s_i$，我们可以用扫描线遍历 $t$。利用 Aho-Corasick 算法，对于每个位置 $i$，找到以 $i$ 结尾的、属于 $S$ 的最长子串（记为 $s_j$）。同时，在一个堆或 set 结构中维护所有右端点不超过 $i$ 的询问的起点。对于每个起点晚于 $s_j$ 起点的询问，$s_j$ 都是合法的覆盖子串。所有这些询问随后从堆中移除。

因此，最终方案需要构建正向和反向的 Aho-Corasick 自动机，并用扫描线遍历 $t$，配合堆维护查询。总复杂度为 $O(S + |t| + m \log m)$。