题目大意

我们有两个命名串：

• 去年的命名串是 $S$ 的某个子串 $S[l..r]$（$S$ 是已知的固定串）
• 今年的命名串是 $T$（每次询问可能不同）

题目要求：找出所有满足以下条件的命名方案数：

1. 是今年命名串 $T$ 的非空连续子串
2. 一定不会出现在去年命名串 $S[l..r]$ 中

---

核心思路分析

第一步：转化问题

设：

• $A$ = $T$ 的所有不同非空子串个数
• $B$ = 同时出现在 $T$ 和 $S[l..r]$ 中的不同子串个数

那么答案就是：

$$\text{答案} = A - B$$

因为我们要找的是在 $T$ 中但不在 $S[l..r]$ 中的子串。

---

第二步：计算 $A$

$T$ 的所有不同非空子串个数可以用后缀自动机（SAM）轻松求出。

对于字符串 $T$，建立其 SAM，那么：

$$A = \sum_{u \in \text{SAM}(T)} (\text{len}(u) - \text{len}(\text{link}(u))) $$

其中 $\text{len}(u)$ 表示状态 $u$ 能接受的最长子串长度。

---

第三步：计算 $B$

这是本题的难点：求两个字符串的公共子串个数，但其中一个字符串是固定长串 $S$ 的子区间。

3.1 对 $S$ 建立后缀自动机

由于所有询问的 $S[l..r]$ 都来自同一个母串 $S$，我们可以预先为整个 $S$ 建立 SAM。

3.2 在 $S$ 的 SAM 上匹配 $T$

我们让 $T$ 在 $S$ 的 SAM 上运行，同时记录：

• 当前匹配长度 cur_len
• 当前状态 state

对于 $T$ 的每个前缀 $T[1..i]$，我们想知道它与 $S[l..r]$ 的最长公共后缀长度。

3.3 处理区间限制 $[l, r]$

关键问题：$S$ 的 SAM 接受的是整个 $S$，但我们需要只考虑 $S[l..r]$ 的子串。

解决方案：使用线段树合并预处理每个 SAM 状态的 endpos 集合，然后检查当前状态是否能出现在区间 $[l, r]$ 中。

具体步骤：

1. 对 $S$ 的 SAM 的每个状态，用线段树合并记录其所有 endpos
2. 匹配 $T$ 时，维护 (state, cur_len) 表示当前匹配状态和长度
3. 如果当前状态的 endpos 在 $[l, r]$ 中有出现，说明匹配成功
4. 否则，沿着后缀链接 link 回退，直到找到在 $[l, r]$ 中有出现的状态

3.4 计算公共子串个数

对于 $T$ 的每个位置 $i$，我们得到以 $i$ 结尾的与 $S[l..r]$ 的最长公共子串长度 $L_i$。

那么所有公共子串个数为：

$$B = \sum_{i=1}^{|T|} L_i$$

因为对于每个结束位置 $i$，长度 $1$ 到 $L_i$ 的子串都是公共的，且不会重复计数（这些子串的结束位置不同）。

---

第四步：算法流程

1. 预处理：

   • 对母串 $S$ 建立后缀自动机
   • 对 SAM 进行线段树合并，记录每个状态的 endpos 集合

2. 处理每个询问：

   • 读取 $T, l, r$
   • 计算 $A$ = $T$ 的不同子串数（用 $T$ 的 SAM）
   • 计算 $B$ = $T$ 与 $S[l..r]$ 的公共子串数：
     • 初始化 state = root, cur_len = 0, B = 0
     • 对于 $i = 1$ 到 $|T|$：
       • 沿着 SAM 的转移边前进，同时保持 state 在 $[l, r]$ 区间内有效
       • 更新 cur_len 和 state
       • 如果无法前进，沿后缀链接回退直到可以继续
       • $L_i$ = 当前的 cur_len
       • $B$ += $L_i$
   • 输出 $A - B$

---

时间复杂度

• 预处理 $S$ 的 SAM 和线段树合并：$O(|S| \log |S|)$
• 每个询问：$O(|T| \log |S|)$
• 总复杂度：$O(|S| \log |S| + \sum |T| \log |S|)$

---

样例解析

以第一个询问为例：

S = "scbamgepe"
T = "smape", l=2, r=7 → S[2..7] = "cbamge"

• $T$ 的所有不同子串：很多，计算得 $A = 15$
• $T$ 与 "cbamge" 的公共子串："m", "a", "p", "ma" 等，计算得 $B = 3$
• 答案 = $15 - 3 = 12$

---

代码实现要点

1. 使用结构体实现 SAM，支持动态添加字符
2. 线段树合并时使用动态开点
3. 匹配时注意处理回退情况
4. 注意数组大小，避免 MLE

---

总结

本题综合运用了：

• 后缀自动机（SAM）
• 线段树合并
• 区间子串查询
• 双字符串匹配

关键突破点是将"与区间子串的公共子串计数"转化为在全局 SAM 上的匹配问题，通过线段树合并解决区间限制。