Dydaktyka‎ > ‎Notatki‎ > ‎

Odległość edycyjna

opublikowane: 3 mar 2011, 08:23 przez Rafał Nowak   [ zaktualizowane 26 lut 2015, 09:03 przez Rafał Nowak ]
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 destokoroltka (skreślone i czerwone znaki oznaczają edycję).

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