8

重複の可能性:
ある順列を別の順列に変換するために必要なスワップのカウント

許可されている操作のみが2つの隣接する文字の転置である、ある種の文字列距離をカウントするアルゴリズムを探しています。例:
string1: "mother"
string2: "moterh"
distance: 2 (最初に "h" を "e" に置き換えて "motehr" を取得し、次に "h" を "r" に置き換えて "moterh"
を取得します) –レーベンシュタイン距離はその問題と非常によく似ていますが、多くのメモリが必要です (1000000 文字までの単語で非常に高速に動作することを望みます)。私はすでにこれを書いています：

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

基本的に、編集距離アルゴリズムを要求していますが、転置 (別名スワッピング、ひねり) 操作のみを許可しています。「Introduction to Algorithms」という本には、ひねり操作を実装するための手がかりが見つかります。これは、動的計画法に関する章の最後にある問題の 1 つです。また、本「アルゴリズム設計マニュアル」の動的プログラミングの章では、C での編集距離アルゴリズムの完全な実装があります-転置操作はありません (繰り返しますが、これは章の最後に提案されている演習の 1 つです)。 ）。

上記のリンクでは、編集距離アルゴリズムを実装する一般的な方法は、動的計画法を使用することであることがわかります。これには、O(mn) 時間と O(mn) スペースのコストがかかります。私の知る限り、より速く (たとえば、O(mn) 時間未満で) 行う方法はありませんが、確かに、より少ないスペースでそれを行うことができます。転置操作のコストを計算するには、テーブルの現在の行と前の 2 つの行のみが必要です。

つまり、編集距離のみが必要であると仮定します。実際の編集操作が必要な場合、動的計画法を使用している場合、ソリューションを再構築するために O(mn) スペースを使用することになります。ただし、 Hirschberg のアルゴリズムを使用して、スペースを O(min{m,n}) に減らし、実際の編集操作を再構築できます。

于 2011-10-25T20:27:16.673 に答える