summaryrefslogtreecommitdiff
path: root/Year_2/Algorithms
diff options
context:
space:
mode:
authorSanto Cariotti <santo@dcariotti.me>2023-01-20 13:40:59 +0100
committerSanto Cariotti <santo@dcariotti.me>2023-01-20 13:40:59 +0100
commitb3137f76e4c0358cededffd49153d159a8f97d9a (patch)
treec437fc2b47af010be21391dec4956254c7e8e9a2 /Year_2/Algorithms
parenta9aba4bcf7052cd832fe63188a44d72375d857ce (diff)
add edit for levenshtein
Diffstat (limited to 'Year_2/Algorithms')
-rw-r--r--Year_2/Algorithms/edit.cc63
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;
+}