Comparaison de chaînes efficace

Question

J'ai essayé d'implémenter un algorithme de comparaison de chaînes efficace qui donnera des points en fonction des changements de caractères.

Par exemple:

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

Ici Chaîne # 2 caractère c il a changé son index de 2 à 1, et d changé son indice de 4 à 3. Les deux d'entre eux (2-1=1 et) ajoute à 2 points au point initial. Pas un devoir ou quoi que ce soit, je ne voulais pas créer une base pour la boucle de comparer chaque caractère un par un et je voulais savoir si quelque chose de méthode efficace (comme le hachage, etc.) peut être appliquée?

Answer 1

Vous complimentez une chose simple. Vous ne pouvez pas obtenir plus efficace que de comparer chaque caractère et d'arrêter la comparaison au premier caractère que vous trouvez différent - ce qui est essentiellement ce que fait strcmp. La seule optimisation typique que vous pouvez faire est, si vous connaissez déjà la longueur des deux chaînes (comme cela se produit lorsque vous utilisez std::string ou d'autres chaînes comptées), pour les déterminer immédiatement si les deux longueurs diffèrent.

Answer 2

Il semble que ce que vous voulez vraiment, c'est quelque chose comme la distance de Levenshtein (mais pas exactement cela). Voici une première coupe.

Ce qu'il fait est de marcher l'arbre de jeu de tous les réarrangements possibles de un pour voir si elles correspondent b. Il associe un coût à chaque réarrangement, exprimé par un budget en baisse.

La boucle externe marche d'abord avec un budget de 0, donc seule une correspondance exacte est autorisée.

S'il n'a pas eu de succès, alors il marche avec un budget de 1, trouvant toutes les correspondances contenant un seul réarrangement.

S'il n'a pas eu de succès, alors il marche avec un budget de 2, et ainsi de suite.

Comme il correspond, il conserve un tableau d'entiers delta, dire à quel point chaque élément de un a été échangé. Chaque fois qu'il obtient un succès, il affiche parfois ce tableau delta, et c'est votre dossier de ce que les swaps ont été faits pour obtenir ce match.

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); 
    } 
} 

La performance de l'algorithme est exponentielle N, où N est le nombre minimum de réarrangements nécessaires pour rendre le match des cordes. Il ne devrait donc probablement pas être utilisé tant que vous n'avez pas vérifié que chaque chaîne a le même nombre de caractères, , et ne l'utilisez que si vous avez besoin de voir cet enregistrement de réarrangements.