Porównanie stringów

Porównanie stringów
GO
  • Rejestracja:około 6 lat
  • Ostatnio:19 dni
  • Postów:92
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?

AK
  • Rejestracja:prawie 7 lat
  • Ostatnio:około 2 miesiące
  • Postów:3561
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


Bo C to najlepszy język, każdy uczeń ci to powie
edytowany 1x, ostatnio: AnyKtokolwiek
mwl4
  • Rejestracja:ponad 12 lat
  • Ostatnio:około miesiąc
  • Lokalizacja:Wrocław
  • Postów:399
0

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

Kopiuj
#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


Asm/C/C++
edytowany 1x, ostatnio: mwl4
GO
  • Rejestracja:około 6 lat
  • Ostatnio:19 dni
  • Postów:92
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

lion137
To trochę twist od oryginalnego tematu...
GO
bo myślałem, że jeśli jest funkcja która zwróci na których pozycjach dwa stringi są różne to też będzie OK
lion137
Niestety nie będzie
_13th_Dragon
  • Rejestracja:prawie 20 lat
  • Ostatnio:20 dni
0

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


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
lion137
Chciałem to powiedzieć, edit distance
GO
  • Rejestracja:około 6 lat
  • Ostatnio:19 dni
  • Postów:92
0

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

EL
  • Rejestracja:ponad 4 lata
  • Ostatnio:około 3 godziny
  • Postów:139
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.

edytowany 1x, ostatnio: eleventeen
_13th_Dragon
Przecież to znany fakt odległość levenshteina kiepsko działa na krótkich napisach
MarekR22
radzę doczytać jak działa Levenshtein. Można skorzystać z uogólnienia i zdefiniować rożne operacje i dla każdej operacji inną odległość.
jarekr000000
@MarekR22: autokorekta wygrała internety

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.