CF1801G A task for substrings
Alex_Wei
·
·
题解
*CF1801G A task for substrings
给出 在线 且 空间线性（字符集大小为常数）的做法。
设 f_i 表示 T[1, i] 的后缀有多少个是单词，g_i 表示最长的为 T[1, i] 的后缀的单词编号，h_i 表示 f 的前缀和。
对于每组询问，直接用 h_r - h_{l - 1} 回答询问，相当于求出了右端点在 [l, r] 的子串单词数量，但没有保证左端点在 [l, r] 范围内。
考虑找到最大的 q 使得 q - |s_{g_q}| + 1 \leq l，那么以 q + 1\sim r 为右端点的合法子串单词数量就等于 h_r - h_q，以 l\sim q 为右端点的合法子串数量就等于 s_{g_q} 的长度为 q - l + 1 的后缀有多少个子串是单词。
设 c_{i, j} 表示编号为 i 的单词的长度为 j 的后缀有多少个子串是单词，总状态数 S，建反串 ACAM 预处理。
时间复杂度 $\mathcal{O}(S + |t| + m\log |t|)$。不难看出算法是 **在线** 的。[代码](https://codeforces.com/contest/1801/submission/209630341)。