Algorithme pour une chaîne de caractères avec un seul désaccord

Question

Quelqu'un pourrait-il suggérer une meilleure approche pour une comparaison de deux chaînes de caractères avec au moins une non-concordance ?

Exemple :

• A : abcdefghabX
• B : abc
• Sortie : 1 9

Les sorties ci-dessus sont les positions des correspondances des sous-chaînes de abc dans "A".

J'ai essayé l'approche de base avec deux boucles for mais il semble que cela prenne N*N temps. C'est un facteur important pour les grandes entrées et cela prend énormément de temps.

Mon algorithme est comme tel, mais il n'est pas le meilleur pour une grande quantité de données.

int compare(string a,  int pos, string b)
{
    int count = 0;
    int length = b.length()-1;
    int mid = b.length() /2;

    if(pos+length >= a.length())
        return 0;
    if((length+1)%2 != 0)   {
        for(int i=0,j=pos;i<=mid;i++,j++)   {       
            if(i == mid)    {
                if(a[j] != b[i])
                    count ++;
            }
            else    {
                if(a[j] != b[i])
                    count ++;
                if(a[pos+length - i] != b[length -i]) 
                    count ++;
            }
            if(count >= 2) return 0;
        }
    }
    else    {
        for(int i=0,j=pos;i<mid;i++,j++)    {       
            if(i == mid)    {
                if(a[j] != b[i])
                    count ++;
            }
            else    {
                if(a[j] != b[i])
                    count ++;
                if(a[pos+length - i] != b[length -i]) 
                    count ++;
            }
            if(count >= 2) return 0;
        }
    }
    return 1;
}

Answer 1

Ce que vous voulez est implémenté dans agrep, alors jetez un coup d'œil à la section algorithmes qu'il utilise.

Answer 2

Je pense que ce que vous cherchez est le Boyer-Moore algorithme.

Plus précisément, la version approximative aquí .