旧前缀可替代嵌入不足以判别中性

lesson fact method principle predicate verification witness normalization 4360dd15

修改:20260425013950000

旧前缀可替代嵌入不足以判别中性


在触及 greedy witness 之后,不能只检查“原始已匹配前缀 S[:k] 在交换后是否仍可嵌入”。

# 反例
- X = ab, S = ba, i = 0
- 原始 k = 1,因为 S[:1] = b ⪯ X
- 交换后 X' = ba,此时 k' = 2
- 尽管旧前缀 S[:1]X' 中仍可嵌入,判定却已经变敏感

# 结论
“旧前缀可替代嵌入”只是必要信息,不是充要判别。
真正的判别必须进一步比较:
1. 交换后是否出现更长的新前缀可行性;
2. 可行的替代嵌入是否会把 greedy 路径推进到更深层;
3. 触及 witness 后,必须看整体可达前缀上界,而不是只看原前缀是否幸存。