summaryrefslogtreecommitdiff
path: root/Year_2/Algorithms
diff options
context:
space:
mode:
authorSanto Cariotti <santo@dcariotti.me>2023-01-20 12:14:18 +0100
committerSanto Cariotti <santo@dcariotti.me>2023-01-20 12:14:18 +0100
commita9aba4bcf7052cd832fe63188a44d72375d857ce (patch)
treeaf87e6ace51e3a94b136b7c4de01d736a95fba8d /Year_2/Algorithms
parentf5276526eb7f5ad1d3a97dc555977d0196b4c796 (diff)
add lcs
Diffstat (limited to 'Year_2/Algorithms')
-rw-r--r--Year_2/Algorithms/lcs.cc88
-rw-r--r--Year_2/Algorithms/print-lcs.cc91
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;
+}