单侧交换位置可压缩为局部窗口

单侧交换位置可压缩为由 greedy witness 决定的局部窗口

设左块为纯字母串 X，目标串为 S（不含 μ），并令

k = max { t | S[:t] ⪯ X }。

取 S[:k] 在 X 中的最左贪心嵌入位置序列 p1 < p2 < ... < pk。
那么：

- 若一次相邻交换的位置 i < p1 - 1，则这次交换不可能影响 S[:k] 的贪心嵌入，因此 k 不变；
- 若 i > pk，同理也不会影响 k；
- 因而，只有落在窗口 i ∈ [p1-1, pk] 内的相邻交换，才值得继续判定。

换句话说，'允许交换的位置' 可以从整个 X 压缩成一个由当前 witness 直接给出的局部窗口，而不必对所有位置逐一检查。

经验

这个窗口不是先验给定的，而是由 S[:k] 的 greedy witness 决定；所以正确的流程是：
1. 先算出 k 和 witness 位置 p1..pk；
2. 再把候选交换限制到窗口内；
3. 最后只在窗口内验证交换是否改变 k。

机器复核

对二元字母表上 |X|,|S| ≤ 7 的穷举没有找到反例：窗口外的交换都保持 k 不变。