字符串距离,仅限换位

Question

可能重复:
计算将一个排列转换为另一个排列所需的交换

我正在寻找一种计算某种字符串距离的算法,其中只允许操作是两个相邻字符的转置.例如:
string1:"mother"
string2:"moterh"
距离:2(首先交换"h"与"e"并获得"motehr"然后"h"与"r"导致"moterh")
我知道Damerau -Levenshtein距离这个问题非常相似,但它需要大量的内存(我希望它可以在高达1 000 000个字符的单词上工作得非常快).我已经写过:

int amo = 0;

for (int i = 0; i < n; i++)
{
    if (fromString[i] == toString[i])
        continue;
    char toWhat = toString[i];
    int where = -1;
    for (int j = i; j < n; j++)
    {
        if (fromString[j] == toWhat)
        {
            where = j;
            break;
        }
    }
    while (where != i)
    {
        char temp = fromString[where];
        fromString[where] = fromString[where - 1];
        fromString[where - 1] = temp;
        where--;
        amo++;
    }
}
cout << amo << endl;`

字符串表示为char [n],其中n是它们的长度.我很确定有一种方法可以更快地完成它,如果有人会告诉我如何操作或编写一些源代码(最好的是Java/Python/C++,但任何事情都很棒),我会非常感激.

PS对不起任何语言错误,我不是英语,我还没有掌握那种语言.

Answer 1

基本上你要求编辑距离算法,但只允许转置(也就是交换,twiddling)操作.在"算法简介"一书中,您将找到实现旋转操作的线索,这是动态编程章节末尾的问题之一.此外,在"算法设计手册"一书中,在动态编程一章中,C语言编辑距离算法的完整实现 - 转换操作(同样,它是本章末尾提出的练习之一) ).

在上面的链接中,您会发现实现编辑距离算法的典型方法是使用动态编程,其成本为O(mn)时间和O(mn)空间.据我所知,没有办法更快地完成它(例如在不到O(mn)的时间内),但肯定你可以在更小的空间内完成 - 聪明,你可以将空间减少到O(m),给定只需要表中的当前行和前两行来计算转置操作的成本.

也就是说,假设您只需要编辑距离.如果您需要实际的编辑操作,如果使用动态编程,则会使用O(mn)空间来重建解决方案.但是,您可以使用Hirschberg的算法将空间减小到O(min {m,n})并重建实际的编辑操作.