8

可能重复：
计算将一种排列转换为另一种排列所需的交换次数

我正在寻找一种算法来计算某种字符串距离，其中只允许操作是两个相邻字符的转置。例如：
string1: "mother"
string2: "moterh"
distance: 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 请原谅我的语言错误，我不是英语，我还没有掌握那种语言。

4

1 回答 1

5

基本上你要求编辑距离算法，但只允许转置（又名交换，旋转）操作。在“算法简介”一书中，您会找到实现旋转操作的线索，这是动态规划一章末尾的问题之一。此外，在“算法设计手册”一书中，在动态规划一章中，有一个完整的 C 语言编辑距离算法实现 - 没有转置操作（同样，这是本章末尾建议的练习之一）。

在上面的链接中，您会发现实现编辑距离算法的典型方法是使用动态规划，这需要 O(mn) 时间和 O(mn) 空间。据我所知，没有办法更快地做到这一点（例如，在少于 O(mn) 的时间内），但你肯定可以在更少的空间内做到这一点 - 聪明，你可以将空间减少到 O(m)，给定计算转置操作的成本只需要表中的当前行和前两行。

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

于 2011-10-25T20:27:16.673 回答