Advertisement
Guest User

Untitled

a guest
Dec 5th, 2019
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4.  
  5.  
  6. int main() {
  7. char* string1 = new char[1001];
  8. char* string2 = new char[1001];
  9. cin.getline(string1, 1001);
  10. cin.getline(string2, 1001);
  11. int size1 = strlen(string1);
  12. int size2 = strlen(string2);
  13. int** answer = new int*[size1 + 1];
  14. for (int i = 0; i < size1 + 1; ++i) {
  15. answer[i] = new int[size2 + 1];
  16. }
  17. for (int j = 0; j <= size2; ++j) {
  18. answer[0][j] = j;
  19. }
  20. for (int i = 0; i <= size1; ++i) {
  21. answer[i][0] = i;
  22. }
  23. for (int i = 1; i <= size1; ++i) {
  24. for (int j = 1; j <= size2; ++j) {
  25. answer[i][j] = min(answer[i][j - 1] , answer[i - 1][j]) + 1;
  26. if (string1[i - 1] == string2[j - 1]) {
  27. answer[i][j] = min(answer[i][j], answer[i - 1][j - 1]);
  28. } else {
  29. answer[i][j] = min(answer[i][j], answer[i - 1][j - 1] + 1);
  30. }
  31. }
  32. }
  33. cout << answer[size1][size2];
  34. for (int i = 0; i <= size1; ++i) {
  35. delete []answer[i];
  36. }
  37. delete []answer;
  38. return 0;
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement