交换不依赖右侧的充分条件

交换不依赖右侧的充分条件

设 L = X · μ · Y，X' 由 X 中一次相邻交换得到。若对任意目标串 S，交换前后左块的最大前缀消耗量

k(X,S) = max { t | S[:t] ⪯ X }

满足 k(X,S) = k(X',S)，则对任意右侧 Y 有：

S ⪯ X · μ · Y ⇔ S ⪯ X' · μ · Y

换言之，**交换是否影响整体可行性，只取决于它有没有改变左块对 S 的 greedy 前缀消耗量**；右侧 Y 在这个充分条件下是惰性的。

机器检验过的边界

- 如果某个 S 使 k(X,S) ≠ k(X',S)，则确实可能存在某个 Y 让两边可行性不同；
- 在 small-case 穷举里，没有发现“可行性不同但 k 相同”的反例。

方法意义

这给“锚定 marker 后的局部交换”提供了一个更稳定的判据：
先比较交换是否改变左块的 greedy 消耗量，再决定是否需要查看右侧。