1

JavaScript で 2 つの文字列を比較したいのですが、他の文字列と異なる正確な位置を見つける必要があります。

例えば

StingA= "a;b;c;"
StringB="a;bc;"

上記から、StringB は位置 3 で StringA とは異なります。つまり、「;」[a=0,;=1,b=2 のカウントを開始した場合];

非常に大きな文字列、つまり StringA="a;b;c;d;e;f;g; ....." が存在する可能性があるため、文字ごとに比較することはできません。

解決策を教えてください。

4

1 に答える 1

0

アルゴリズムのプロファイリングを既に行っていて、それが遅すぎると判断した場合を除き、パフォーマンスの最適化について心配する必要はありません。最初に動作するアルゴリズムを取得してから、必要に応じてプロファイリングします。

// Returns the index of the first difference between strings a and b,
// or -1 if the strings are equal. Case-sensitive.
function indexOfDiff(a, b) {
    if(a === b) {
        return -1;
    }

    var len = Math.min(a.length, b.length);
    for(var i = 0; i < len; i++) {
        if(a.charAt(i) !== b.charAt(i)) {
            return i;
        }
    }

    return len;
}

絶対にパフォーマンスが必要な場合は、「;」の既知の位置に基づいてヒューリスティックなアプローチを試すことができます。（あなたの例のように、文字とセミコロンが交互になっていることがわかっている場合は、他のすべての文字をチェックできます）。

または、非常に大きな文字列の場合は、再帰的な二分探索を試すことができます。1 つの文字列を半分に分割し、他の文字列の同等の部分文字列と等しいかどうかを確認します。等しい場合は、残りの半分を確認します。等しくない場合は、その文字列を半分に分割し、適切なサイズの部分文字列を絞り込んでチェックするまで、このプロセスを繰り返します。このアプローチははるかに複雑でエラーが発生しやすいため、最初に単純なアプローチを試してください。

于 2013-01-23T19:00:38.820 に答える