题目理解

我们有一个初始为空的字符串 $S$，每次在末尾添加一个字符（数字），每次操作后需要求出当前字符串中不同非空子串的数量。

换句话说，设第 $i$ 次操作后的字符串为 $S_i$，我们需要求： [ f(i) = \text{S_i 中不同非空子串的数量} ]

---

问题分析

1. 不同子串数量的经典求法

对于一个长度为 $n$ 的字符串，不同子串数量为： [ \text{总子串数} - \text{重复计算的子串数} = \frac{n(n+1)}{2} - \sum_{i=1}^{n-1} \text{LCP}(i,i+1) ] 其中 $\text{LCP}(i,j)$ 表示后缀 $i$ 和后缀 $j$ 的最长公共前缀。

更常用的方法是使用后缀自动机 (Suffix Automaton)：

• 后缀自动机的每个节点代表一组 endpos 等价类
• 不同子串数量 = $\sum_{u \in \text{SAM}} (\text{len}(u) - \text{len}(\text{link}(u)))$
• 其中 $\text{len}(u)$ 表示节点 $u$ 能接受的最长字符串长度

---

算法设计

方法：动态构建后缀自动机

后缀自动机非常适合本题，因为：

1. 在线性时间内支持在末尾添加字符
2. 每次添加后可以立即更新答案

后缀自动机核心思想：

• 每个节点表示一个 endpos 等价类
• $\text{len}(u)$：该节点代表的最长子串长度
• $\text{link}(u)$：后缀链接，指向更短的等价类
• 不同子串数量 = 所有节点的 $(\text{len}(u) - \text{len}(\text{link}(u)))$ 之和

动态更新过程：

设当前答案为 $ans$，当添加字符 $c$ 时：

1. 创建新节点 $cur$，$\text{len}(cur) = \text{len}(last) + 1$
2. 从 $last$ 开始沿后缀链接遍历，为没有 $c$ 转移的节点添加指向 $cur$ 的转移
3. 如果找到第一个有 $c$ 转移的节点 $p$，设 $q = \text{next}(p, c)$
4. 如果 $\text{len}(q) = \text{len}(p) + 1$，直接设置 $\text{link}(cur) = q$
5. 否则需要分裂节点 $q$，创建新节点 $clone$
6. 更新答案：$ans \leftarrow ans + (\text{len}(cur) - \text{len}(\text{link}(cur)))$

---

具体实现细节

1. 数据结构

struct Node {
    int len, link;
    map<int, int> next;  // 因为字符值范围大，用map存储转移
};

vector<Node> sam;
int last;
long long ans;  // 当前不同子串数量

2. 初始化

void sam_init() {
    sam.push_back({0, -1, {}});
    last = 0;
    ans = 0;
}

3. 添加字符

void sam_extend(int c) {
    int cur = sam.size();
    sam.push_back({sam[last].len + 1, 0, {}});
    
    int p = last;
    while (p != -1 && !sam[p].next.count(c)) {
        sam[p].next[c] = cur;
        p = sam[p].link;
    }
    
    if (p == -1) {
        sam[cur].link = 0;
    } else {
        int q = sam[p].next[c];
        if (sam[p].len + 1 == sam[q].len) {
            sam[cur].link = q;
        } else {
            int clone = sam.size();
            sam.push_back({sam[p].len + 1, sam[q].link, sam[q].next});
            while (p != -1 && sam[p].next[c] == q) {
                sam[p].next[c] = clone;
                p = sam[p].link;
            }
            sam[q].link = sam[cur].link = clone;
        }
    }
    
    ans += sam[cur].len - sam[sam[cur].link].len;
    last = cur;
}

---

复杂度分析

• 时间复杂度：每次添加字符的均摊复杂度为 $O(\log \Sigma)$，其中 $\Sigma$ 是字符集大小（这里用 map 存储转移）
• 总复杂度：$O(n \log \Sigma)$
• 空间复杂度：$O(n)$

---

样例验证

输入：

7
1 2 3 3 3 1 2

逐步分析：

1. 添加 1：子串 [1]，数量 = 1
2. 添加 2：子串 [1], [2], [1,2]，数量 = 3
3. 添加 3：子串增加 [3], [2,3], [1,2,3]，数量 = 6
4. 添加 3：子串增加 [3,3], [2,3,3], [1,2,3,3]，数量 = 9
5. 添加 3：子串增加 [3,3,3], [2,3,3,3], [1,2,3,3,3]，数量 = 12
6. 添加 1：子串增加 [1], [3,1], [3,3,1], [3,3,3,1], [2,3,3,3,1], [1,2,3,3,3,1]，但 [1] 已存在，实际增加5个，数量 = 17
7. 添加 2：子串增加 [2], [1,2], [3,1,2], [3,3,1,2], [3,3,3,1,2], [1,2,3,3,3,1,2]，但 [2], [1,2] 已存在，实际增加4个，数量 = 21？等等，检查...

仔细计算第7步：

• 新后缀：2, 12, 312, 3312, 33312, 233312, 1233312
• 重复的：2, 12 之前出现过
• 实际新增：312, 3312, 33312, 233312, 1233312 共5个
• 17 + 5 = 22 ✓

输出：

1
3
6
9
12
17
22

完全匹配。

---

总结

本题的关键在于：

1. 理解不同子串数量的计算方法
2. 掌握后缀自动机的构建原理
3. 利用后缀自动机的在线性和动态更新特性
4. 注意字符集较大时使用 map 存储转移

后缀自动机是解决这类"动态求不同子串数量"问题的利器，时间复杂度优秀且代码相对简洁。