c++ - zig zag字符串的最小编辑距离

Question

我有这样的字符串 xxoxxooo，我想将它编辑成这种形式 xoxoxoxo，我的问题是如何找到最小交换次数，我只能交换 2 个邻居作为交换。我考虑过遍历字符串并找到最接近的冗余 x 并将其移动到当前位置，但我认为那太慢了，因为字符串可以有 1e6 * 2 个字符。有什么想法吗？

Answer 1

让 s_i 表示位置 i 和 i+1 之间的交换

假设您有一个从 A 到 B 的最小交换序列 S = s_{i1} s_{i2} ... .因为它是最小的，所以你只能将 x 与 o 交换，而不能将 x 与 x 或 交换o 与 o。因此S的 Action 是将A的第一个o发送给B的第一个o ，A的第二个o到B的第二个o，依此类推。因此swap的数量不能小于

Sum_i abs(pos of i-st o in A - pos of i-st o in B)

现在很容易找到恰好具有此交换次数的序列，因此这是正确的值。

这是一个计算它的算法

Input: s1 and s2 of common length n
I'm assuming that they contains the same number of 'x' and 'o'

res = 0;
i1 = 0; i2 = 0;
while true do
    // find the next o
    while i1 < n and s1[i1] == 'x' do
        i1++
    if i1 == n return res
    // no check that i2 < n because of assumption
    while s2[i2] == 'x' do 
        i2++
    res += abs(i1-i2)
    i1++; i2++