Porównanie stringów

0

Witam
Czy jest w c++ jakaś funkcja, albo metoda klasy string, która pozwala określić na ilu dokładnie pozycjach różnią się dwa stringi?

5

Na tych samych pozycjach? napisz na kolanie

Na różnych? -> https://pl.wikipedia.org/wiki/Odleg%C5%82o%C5%9B%C4%87_Levenshteina
jest wiele implementacji w sieci

0

Nie ma takiej funkcji w bibliotece standardowej. Musisz ją napisać sam.

#include <iostream>
#include <string>

using namespace std;

unsigned int compare_with_difference_count( const string &a, const string &b )
{
    unsigned int result = 0;

    const size_t a_len = a.length();
    const size_t b_len = b.length();
    const size_t max_len = max( a_len, b_len );
    const size_t min_len = min( a_len, b_len );

    for( size_t pos = 0; pos < max_len; ++pos )
    {
        if( pos >= min_len )
        {
            result += max_len - pos;
            break;
        }

        if( a[ pos ] != b[ pos ] )
        {
            ++result;
        }
    }
    return result;
}

int main()
{
    const string a = "Ala ma kota";
    const string b = "Ala ma psa";
    const int diff_count = compare_with_difference_count( a, b ); // prints 4
    cout << diff_count << endl;

    const string c = "Ala ma psa";
    const string d = "Ala ma chomika";
    const int diff_count2 = compare_with_difference_count( c, d ); // prints 7
    cout << diff_count2 << endl;
    return 0;
}

Tu zastosowałem bardzo prosty algorytm, który sprawdza zawsze te same pozycje. Jeśli chcesz znaleźć różnice w dwóch stringach to potrzebujesz znacznie bardziej wyrafinowanego algorytmu. Na przykład Git używa czterech różnych: Myers, Minimal, Patience, i Histogram: https://link.springer.com/article/10.1007/s10664-019-09772-z

0

Może to będzie to o co mi chodzi, bo mam za zadanie napisać funkcję, która akceptuje dwa stringi i zwróci prawda, jeśli między stringami a i b zostały przeprowadzone następujące operacje, został wstawiony jedne znak, lub został usunięty jeden znak, lub zamienione miejscami dwa znaki

0

No to prawie na 100% odległość Levinsteina.

0

Dziękuję za odpowiedzi. Postaram się zaimplementować ten algorytm

0
gonskabalbinka napisał(a):

Postaram się zaimplementować ten algorytm

Nie radze. Po zaimplementowaniu levenshteina:

  • wyniki beda bledne (np. po zamianie miejscami znakow w stringu "12" wynik to bedzie 2. zamiana tego stringa np. na "55" tez da wynik 2)
  • wolne to bedzie. zlozonosc algorytmu ktory masz zaimplementowac moze byc duzo mniejsza

Ciekawe czy tworca zadania przewidzial ze po zamianie miejscami znakow w stringu "11" wedlug przedstawionego opisu funkcja powinna zwrocic true.

1 użytkowników online, w tym zalogowanych: 0, gości: 1