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

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

构建与计数¶

逐字符扩展后缀自动机。状态 \(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 实现。程序仍使用完整的94字符集。

代价与适用条件¶

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