旧前缀可替代嵌入不足以判别中性
lesson fact method principle predicate verification witness normalization 4360dd15
旧前缀可替代嵌入不足以判别中性
在触及 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 后,必须看整体可达前缀上界,而不是只看原前缀是否幸存。