diff options
| -rw-r--r-- | Year_2/Algorithms/edit.cc | 63 |
1 files changed, 63 insertions, 0 deletions
diff --git a/Year_2/Algorithms/edit.cc b/Year_2/Algorithms/edit.cc new file mode 100644 index 0000000..9061006 --- /dev/null +++ b/Year_2/Algorithms/edit.cc @@ -0,0 +1,63 @@ +#include <iostream> +#include <fstream> + +using namespace std; + +int +lev(string x, string y) +{ + int m = x.length() + 1; + int n = y.length() + 1; + int i, j; + + int** c = new int*[m]; + + for (i = 0; i < m; ++i) + c[i] = new int[n]; + + for (i = 0; i < m; ++i) + c[i][0] = i; + + for (i = 0; i < n; ++i) + c[0][i] = i; + + + for (i = 1; i < m; ++i) { + for (j = 1; j < n; ++j) { + int cost = (x[i-1] != y[j-1]); + + c[i][j] = min(min(c[i-1][j]+1, c[i][j-1]+1), c[i-1][j-1]+cost); + } + } + + int r = c[m-1][n-1]; + + for (i = 0; i < m; ++i) + delete[] c[i]; + + delete[] c; + + return r; +} + +int +main(int argc, char** argv) +{ + int ts = (argc > 1) ? stoi(argv[1]) : 100; + ifstream fin("input.txt"); + ofstream fout("output.txt"); + int n, m; + string s1, s2; + + + for (int i = 0; i < ts; ++i) { + fin >> n >> m >> s1 >> s2; + + fout << lev(s1, s2) << endl; + } + + fin.close(); + fout.close(); + + return 0; +} |