diff options
| -rw-r--r-- | Year_2/Algorithms/lcs.cc | 88 | ||||
| -rw-r--r-- | Year_2/Algorithms/print-lcs.cc | 91 |
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; +} |