问题分析

本题是一道基于字典树（Trie） 和栈的字符串动态前缀计数问题，核心任务是计算字符串处理过程中所有出现过的前缀子串的累计出现次数。通过分析代码可知，算法通过栈模拟字符串的插入与删除操作，同时利用字典树记录前缀的出现频率，最终累加所有前缀的贡献值。

算法思路

1. 数据结构设计

• 字典树（Trie）：使用二维数组 sn[N+5][26] 存储节点连接关系，sn[u][c] 表示节点 u 经过字符 c（0-25 对应 a-z）指向的子节点。
• 计数数组：cnt[N+5] 记录每个字典树节点代表的前缀出现的次数。
• 父节点数组：fa[N+5] 存储节点的父节点，用于回溯操作。
• 栈：stk[N+5] 模拟字符串的动态变化（插入/删除），tl 为栈顶指针。
• 当前节点指针：nw 指向字典树中与当前栈状态对应的节点，初始为根节点 0。

2. 核心操作

遍历字符串 s 的每个字符 s[i]（从 1 到 n），分两种情况处理：

（1）字符匹配栈顶（退栈操作）

当栈非空且栈顶字符 stk[tl] 与当前字符 s[i] 相等时：

• 弹出栈顶字符：--tl。
• 回溯到父节点：nw = fa[nw]。
• 累加当前前缀的出现次数到答案，并更新计数：ans += cnt[nw]++。
  （cnt[nw] 是该前缀在本次出现前的累计次数，加 1 后记录本次出现）

（2）字符不匹配栈顶（进栈操作）

否则，将当前字符压入栈：

• 压入字符：stk[++tl] = s[i]。
• 若当前节点有对应子节点（sn[nw][s[i]] 非空）：
  • 移动到子节点：nw = sn[nw][s[i]]。
  • 累加计数：ans += cnt[nw]++。
• 否则，创建新节点：
  • 新建节点 ++tot，记录连接关系：sn[nw][s[i]] = tot。
  • 记录父节点：fa[tot] = nw，移动到新节点：nw = tot。
  • 累加计数：ans += cnt[tot]++（初始计数为 0，加 1 后记录首次出现）。

3. 答案计算

每次操作（进栈/退栈）后，当前节点 nw 对应的前缀均为当前栈所表示的字符串的前缀。答案 ans 累计所有这些前缀在操作时的出现次数，即：

$$\text{ans} = \sum (\text{cnt}[u] \text{ before increment}) $$

其中 u 是每次操作对应的节点。

关键复杂度分析

• 时间复杂度：遍历字符串的每个字符，每个字符的处理（进栈/退栈、字典树操作）均为 $O(1)$（字符集大小固定为 $26$），故总复杂度为 $O(n)$，其中 $n \leq 2 \times 10^6$。
• 空间复杂度：字典树节点总数最多为 $n$（每个字符最多对应一个新节点），空间复杂度为 $O(n \times 26) = O(n)$。

代码解析

模块	功能描述
初始化	读取输入，初始化根节点计数 cnt[0] = 1，栈顶指针 tl = 0。
字符遍历	循环处理字符串的每个字符，判断执行进栈或退栈操作。
退栈逻辑	匹配栈顶时，弹出字符、回溯节点、更新答案与计数。
进栈逻辑	不匹配栈顶时，压入字符、创建或访问子节点、更新答案与计数。
结果输出	输出累计的总答案 ans。

算法的核心是通过栈动态维护当前字符串状态，结合字典树高效跟踪所有前缀的出现次数，在线性时间内完成计算，适合处理大规模字符串输入。