Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstring>
- using namespace std;
- int main() {
- char* string1 = new char[1001];
- char* string2 = new char[1001];
- cin.getline(string1, 1001);
- cin.getline(string2, 1001);
- int size1 = strlen(string1);
- int size2 = strlen(string2);
- int** answer = new int*[size1 + 1];
- for (int i = 0; i < size1 + 1; ++i) {
- answer[i] = new int[size2 + 1];
- }
- for (int j = 0; j <= size2; ++j) {
- answer[0][j] = j;
- }
- for (int i = 0; i <= size1; ++i) {
- answer[i][0] = i;
- }
- for (int i = 1; i <= size1; ++i) {
- for (int j = 1; j <= size2; ++j) {
- answer[i][j] = min(answer[i][j - 1] , answer[i - 1][j]) + 1;
- if (string1[i - 1] == string2[j - 1]) {
- answer[i][j] = min(answer[i][j], answer[i - 1][j - 1]);
- } else {
- answer[i][j] = min(answer[i][j], answer[i - 1][j - 1] + 1);
- }
- }
- }
- cout << answer[size1][size2];
- for (int i = 0; i <= size1; ++i) {
- delete []answer[i];
- }
- delete []answer;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement