在最短公共超串（SCS）问题中，给定一组有限字符串，需要找到长度最短且包含所有输入字符串的超串。该问题是 NP 难的，已有多种近似算法。当前已知的最佳近似比为 $2.466$（Englert、Matsakis 与 Vesel\'y），而 OpenAI 最近宣称已实现 $2$ 的比率。1988 年，Tarhio 与 Ukkonen 提出一种贪心算法：每次合并重叠最长的两条字符串。他们证明该算法的最坏情况长度约为最优解的两倍，并猜想该界限是紧的，即所谓的贪心超串猜想，至今已近四十年未被证伪。已有的上界为 $3.396$（同上）。本文给出以下新结果：
- 通过构造一族实例，证明贪心算法的近似比下界可逼近 $2.4$，从而否定原猜想。
- 证明贪心算法的近似比上界为 $3$。
- 对固定长度 $k$ 的输入字符串，证明当 $k=3$ 时近似比恰为 $9/5$，而当 $k \ge 6$ 时至少为 $2$。
这些结果显著收紧了贪心算法的性能界限，为进一步改进 SCS 近似算法提供了理论依据。\n\n点评：本文不仅给出反例推翻了长期未解的猜想，还给出更紧的上、下界，为实际算法设计提供了明确的性能参考。