Dla danych dwóch słow A i B wyznaczyć ich odległość edycyjną, tzn. ile co najmniej znaków należy usunąć lub wstawić w jednym słowie, aby uzyskać drugie. Na przykład dla słów: deskorolka i stokrotka, ich odległość wynosi 7, bo Oto program w C++, który rozwiązuje ten problem. // Odległość edycyjna dwóch słów #include<iostream> using namespace std; int D[1001][1001]; int main() { int n, m, i, j; string A, B; cin >> A >> B; // wczytaj słowa A i B n = A.size(); m = B.size(); for (i=0; i<=n; i++) D[i][0]=i; for (j=0; j<=m; j++) D[0][j]=j; for (i=1; i<=n; i++) for (j=1; j<=m; j++) if (A[i-1]==B[j-1]) D[i][j] = D[i-1][j-1]; else D[i][j] = min( D[i-1][j], D[i][j-1] ) + 1; cout << D[n][m] << "\n"; return 0; } |