# 告示牌识别：题解

## 解法比较

出题人实现从后往前插入后缀，用 Treap 按“首字符、下一后缀的顺序标签”排序；这是后缀字典序的递归定义。旋转后重标相应子树，标签取浮点区间中点。得到后缀数组和相邻 LCP 后，对每次询问、每个来源分别向左右扫描，求与其他来源的最长公共前缀，再扣掉不能独占的长度，计数依据与下文一致。

标签必须始终严格有序；固定精度中点可能重合，属于需要修复的数值实现问题。出题人实现在一次插入的旋转完成后，还可能重标整棵子树，构造的保守最坏界为 $O(S^2)$ ，询问扫描为 $O(qnS)$ ，空间为 $O(S)$ .Codex（GPT-6）采用的实现使用整数排名的比较排序倍增，构造为 $O(S\log^2(S+1))$ ；各来源的共有长度只预处理一次，扫描与询问共 $O((n+q)S)$ ，空间仍为 $O(S)$ .收益是精确排名、明确的构造界及避免逐询问重复来源扫描；后缀数组与 LCP 计数本身来自出题人解法。

## 对每个起点找最长公共前缀

固定字符串 $s_i$ 中的一个起点 $x$ .令 $h_x$ 为这个后缀与**其他字符串**任意后缀的最长公共前缀长度的最大值。如果没有其他字符串，取零。令 $r_x$ 为从 $x$ 到本串结尾的字符数。

长度不超过 $h_x$ 的前缀还出现在其他串中；长度大于 $h_x$ 的前缀均不在其他串中。因此一次询问的贡献为

$$\max\bigl(0,\min(R,r_x)-\max(L,h_x+1)+1\bigr)$$

对所有起点求和即可。这里没有去除同一字符串中的重复内容，因为题目要求按出现位置计数。

## 后缀数组与相邻 LCP

把所有字符串用互不相同、且不属于小写字母的分隔符连接。记录每个位置所属字符串和 $r_x$ ；分隔符位置的 $r_x=0$ .独特分隔符保证不同后缀的公共前缀不会越过原字符串的边界。

参考实现用倍增构造后缀数组 `Suffix` ：先按首字符，再按两个长度为 $w$ 的排名块排序，将 $w$ 翻倍，直到所有后缀排名互不相同。使用整数排名和比较排序，避免浮点标签。

随后用线性扫描的 LCP 算法求相邻后缀的公共前缀长度。定义 $LCP[j]$ 为排序中第 $j-1$ 与第 $j$ 个后缀的 LCP。任意两个后缀的 LCP 等于它们之间相邻 LCP 的最小值：这些后缀夹在相同字典序前缀区间内，区间最小值决定能共同保留多少字符。

## 只找左右最近的其他来源

对某个来源 $i$ ，从左到右扫描后缀数组。遇到前一个后缀不属于 $i$ 时，从当前相邻 LCP 重新开始；否则持续取最小值。这样得到每个属于 $i$ 的后缀与左侧最近的其他来源后缀的 LCP。反向再扫描一次，得到右侧结果，两者取最大值。

为什么不用比较更远的后缀？到更远后缀的区间包含到最近后缀的区间，最小值只可能更小，不可能更大。因此左右最近候选已经给出 $h_x$ .分隔符可以当作其他来源处理，其与字母开头的后缀 LCP 为零，不会制造错误的公共子串。

## 正确性与复杂度

左右扫描求出了每个起点与其他字符串的最长共有长度；贡献公式恰好保留所有超过此长度、又没有越过本串结尾的询问长度。每个起点和长度唯一确定一次出现，故求和既不遗漏也不重复计数。

令 $S$ 为所有字符串长度之和加分隔符数量。比较排序版倍增的时间为 $O(S\log^2(S+1))$ ；LCP 为 $O(S)$ ；来源扫描与询问共 $O((n+q)S)$ .空间为 $O(S)$ .答案及询问端点使用 64 位整数，即使询问长度远大于字符串，也直接按公式截断。

独立对拍直接枚举所有位置区间，用字符串集合记录出现过的来源，再逐次计数；包括完全相同串、单串、重复字符和很大的询问端点。

## 程序与复现

参考程序见 [std.cpp](std.cpp)。使用 C++17 编译后，可用 `tests/generate.py --out-dir <题目目录以外的路径> --std <程序路径>` 生成输入和答案。固定种子与用例目的见 [生成计划](tests/plan.json)。性能测量见 [评测环境与性能](../../../docs/评测环境与性能.md)。