効率的な文字列の比較

Question

文字の変更に応じてポイントを与える効率的な文字列比較アルゴリズムを実装しようとしています。例えば

：

String #1: abcd 
String #2: acdb 
Initial Point: 0 

はここでは文字列＃2文字cは2から1へのインデックスを変更し、dはそれらの両方（2-1=1と）3に4からのインデックスが変更につながります初期点を2点とする。宿題や何かではなく、私はちょうどそれぞれのキャラクターを1つずつ比較するための基本的なforループを作成したくなく、効率的な方法（ハッシングなど）が適用できるかどうか尋ねたいと思ったのですか？

Answer 1

あなたは単純なことを複雑にしています。それぞれのキャラクターを比較するより効率的になることはできません。異なるキャラクターを見つけた最初のキャラクターで比較を中止することはできません。これは基本的にはstrcmpです。 2つの文字列の長さがすでに分かっている場合（std::stringまたは他のカウント文字列を使用する場合など）、2つの文字列の長さが異なる場合は、すぐに不等号を決定することができます。

Answer 2

あなたが本当に欲しいのは、Levenshtein距離のようなものですが（正確にはそうではありません）。 ここは最初のカットです。それは何

は、彼らがBと一致するかどうかを確認するためにのすべての可能な再配置のゲームツリーを歩いています。 これは、各再配置にコストを関連付けます。これは、の予算がに減少したことで表されます。

まず、外側のループは予算が0であるため、完全一致のみが許可されます。

成功していない場合は、1の予算で歩き、1つの並べ替えを含むすべての一致を見つけます。

成功していない場合は、2の予算で歩いて行きます。

それが一致したとして、それはの各要素が交換されたどこまで言って、整数デルタの配列を保持します。 成功するたびに、somwhowがそのデルタ配列を表示します。それは、そのマッチを得るためにスワップが行われたことの記録です。

void walk(char* a, char* b, int* delta, int budget, int& nSuccess){ 
    delta[0] = 0; 
    if (budget < 0) return; 
    if (a[0] == '\0' && b[0] == '\0'){ // end of both strings 
    nSuccess++; 
    // print out the deltas 
    return; 
    } 
    if (a[0] == '\0') return; // excess chars in b 
    if (b[0] == '\0') return; // excess chars in a 
    if (a[0] == b[0]){ // first chars are equal, move to next 
    walk(a+1, b+1, delta+1, budget, nSuccess); 
    return; 
    } 
    for (int i = 1; a[i] != '\0'; i++){ 
    delta[0] = i; 
    swap(a[0], a[i]); 
    if (a[0] == b[0]){ 
     walk(a+1, b+1, delta+1, budget-1, nSuccess); 
    } 
    swap(a[0], a[i]); 
    delta[0] = 0; 
    } 
} 

void top(char* a, char* b){ 
    int nSuccess = 0; 
    int delta[512]; 
    for (int budget = 0; nSuccess==0; budget++){ 
    walk(a, b, budget, delta, nSuccess); 
    } 
} 

アルゴリズムの性能は、Nは、文字列を一致させるために必要な再配列の最小数であるN、で指数関数的です。 したがって、各文字列の文字数が同じであることを確認してから、 という文字列を確認し、再配置のレコードを確認する必要がある場合にのみ使用してください。