add lcs

2 files changed, 179 insertions, 0 deletions

diff --git a/Year_2/Algorithms/lcs.cc b/Year_2/Algorithms/lcs.cc
new file mode 100644
index 0000000..a7b9361
--- /dev/null
+++ b/Year_2/Algorithms/lcs.cc
@@ -0,0 +1,88 @@
+#include <iostream>
+#include <fstream>
+
+using namespace std;
+
+enum class Arrow {
+	Top,
+	Left,
+	TopLeft,
+};
+
+int
+lcs(string x, string y)
+{
+	int m = x.length()+1;
+	int n = y.length()+1;
+	int** C = new int*[m];
+	Arrow** B = new Arrow*[m];
+	int i, j;
+
+	for (i = 0; i < m; ++i) {
+		C[i] = new int[n];
+		C[i][0] = 0;
+
+		B[i] = new Arrow[n];
+	}
+
+	for (i = 0; i < n; ++i)
+		C[0][i] = 0;
+
+	for (i = 1; i < m; ++i) {
+		for (j = 1; j < n; ++j) {
+			if (x.at(i-1) == y.at(j-1)) {
+				C[i][j] = C[i-1][j-1]+1;
+				B[i][j] = Arrow::TopLeft;
+			} else if (C[i-1][j] >= C[i][j-1]) {
+				C[i][j] = C[i-1][j];
+				B[i][j] = Arrow::Top;
+			} else {
+				C[i][j] = C[i][j-1];
+				B[i][j] = Arrow::Left;
+			}
+		}
+	}
+
+	int r { 0 };
+	for (i = m-1, j = n-1; i != 0 && j != 0; ) {
+		if (B[i][j] == Arrow::TopLeft) {
+			r++;
+			i--;
+			j--;
+		} else if (B[i][j] == Arrow::Top) {
+			i--;
+		} else {
+			j--;
+		}
+	}
+
+	for (i = 0; i < m; ++i) {
+		delete[] C[i];
+		delete[] B[i];
+	}
+	delete[] C;
+	delete[] B;
+
+	return r;
+}
+
+int
+main(int argc, char** argv)
+{
+	int ts = (argc > 1) ? stoi(argv[1]) : 100;
+
+	ifstream fin("input.txt");
+	ofstream fout("output.txt");
+
+	for (int i = 0; i < ts; ++i) {
+		int n;
+		string s1, s2;
+		fin >> n >> n >> s1 >> s2;
+		fout << lcs(s1, s2) << endl;
+	}
+
+	fin.close();
+	fout.close();
+
+	return 0;
+}
diff --git a/Year_2/Algorithms/print-lcs.cc b/Year_2/Algorithms/print-lcs.cc
new file mode 100644
index 0000000..9a0469c
--- /dev/null
+++ b/Year_2/Algorithms/print-lcs.cc
@@ -0,0 +1,91 @@
+#include <iostream>
+#include <fstream>
+
+using namespace std;
+
+enum class Arrow {
+	Top,
+	Left,
+	TopLeft,
+};
+
+void
+lcs(string x, string y, ostream& out)
+{
+	int m = x.length()+1;
+	int n = y.length()+1;
+	int** C = new int*[m];
+	Arrow** B = new Arrow*[m];
+	int i, j;
+
+	for (i = 0; i < m; ++i) {
+		C[i] = new int[n];
+		C[i][0] = 0;
+
+		B[i] = new Arrow[n];
+	}
+
+	for (i = 0; i < n; ++i)
+		C[0][i] = 0;
+
+	for (i = 1; i < m; ++i) {
+		for (j = 1; j < n; ++j) {
+			if (x.at(i-1) == y.at(j-1)) {
+				C[i][j] = C[i-1][j-1]+1;
+				B[i][j] = Arrow::TopLeft;
+			} else if (C[i][j-1] >= C[i-1][j]) {
+				C[i][j] = C[i][j-1];
+				B[i][j] = Arrow::Left;
+			} else {
+				C[i][j] = C[i-1][j];
+				B[i][j] = Arrow::Top;
+			}
+		}
+	}
+
+	string r;
+	for (i = m-1, j = n-1; i != 0 && j != 0; ) {
+		if (B[i][j] == Arrow::TopLeft) {
+			r += x.at(i-1);
+			i--;
+			j--;
+		} else if (B[i][j] == Arrow::Top) {
+			i--;
+		} else {
+			j--;
+		}
+	}
+
+
+	for (i = 0; i < m; ++i) {
+		delete[] C[i];
+		delete[] B[i];
+	}
+	delete[] C;
+	delete[] B;
+
+	for (auto i = r.rbegin(); i != r.rend(); ++i)
+		out << *i;
+	out << endl;
+}
+
+int
+main(int argc, char** argv)
+{
+	int ts = (argc > 1) ? stoi(argv[1]) : 100;
+
+	ifstream fin("input.txt");
+	ofstream fout("output.txt");
+
+	for (int i = 0; i < ts; ++i) {
+		int n;
+		string s1, s2;
+		fin >> n >> n >> s1 >> s2;
+		lcs(s1, s2, fout);
+	}
+
+	fin.close();
+	fout.close();
+
+	return 0;
+}