# 后缀自动机按终点集合计数

Codex（GPT-6）：应用后缀自动机的终点位置等价类，完成计数、程序和验证。该方法是已有字符串算法的应用，不把后缀自动机本身作为模型原创。程序为 [alternative.cpp](alternative.cpp)，与[后缀数组首选解法](solution.zh.md)并列提供。

## 构建与计数

逐字符扩展后缀自动机。状态 $v$ 表示拥有同一终点位置集合的子串，它们的长度恰好覆盖

$$\operatorname{len}(\operatorname{link}(v))+1,\ldots,\operatorname{len}(v).$$

每次扩展产生的新末尾状态计数加1；克隆状态只是分裂等价类，初始计数为0。用长度计数排序后，从长到短把每个状态的计数加入后缀链接状态。得到的计数是该状态各子串的出现次数，重叠位置也会分别贡献。

非初始状态对不同子串数贡献 $\operatorname{len}(v)-\operatorname{len}(\operatorname{link}(v))$ ；仅当该状态出现次数为1时，把同样的贡献加入 $U$ .对全部状态求和得 $D,U$ .

## 正确性

同一状态中的所有字符串具有相同终点集合，因此出现次数一致。每个不同子串恰好对应一个状态及一个允许长度，长度区间求和既不遗漏也不重复。每个前缀末尾标记一次，经后缀链接传播到它的所有后缀等价类，正好统计全部结束位置。因此筛选计数1的状态得到全部唯一子串。

期望为 $ND/U$ ，约分及不可逆分母处理与首选解法的证明相同，由 [expectation.hpp](expectation.hpp) 实现。程序仍使用完整的94字符集。

## 代价与适用条件

状态数不超过 $2n$ ，每个状态含94个转移。时间 $O(94n+Q+\log P)$ ，空间 $O(94n)$ ；把字母表视为固定常数时对 $n$ 为线性。该方案直接按出现次数分类，不需要后缀排序和 LCP，但稠密转移占用更多内存。已通过全部正式输入和独立小规模计数，满足128 MiB及当前时限；实测比较见[首选题解](solution.zh.md)。