diff options
| -rw-r--r-- | PlaygroundCpp/Sources/Playground.cpp | 79 |
1 files changed, 43 insertions, 36 deletions
diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp index 373e327..8c8b854 100644 --- a/PlaygroundCpp/Sources/Playground.cpp +++ b/PlaygroundCpp/Sources/Playground.cpp @@ -1,58 +1,65 @@ #include <iostream> -#include <string> #include <algorithm> +#include <vector> //#include <gtest/gtest.h> -using std::string; +using std::vector; -int editDistance(const string &A, const string &B) { - int m = B.length(); - int n = A.length(); +int lcs2(vector<int> &a, vector<int> &b) { + int m = b.size(); + int n = a.size(); int D[n + 1][m + 1]; - - for (int i = 0; i < n + 1; i++) { - D[i][0] = i; - } for (int j = 0; j < m + 1; j++) { - D[0][j] = j; - } - - for (int j = 1; j < m + 1; j++) { - for (int i = 1; i < n + 1; i++) { - int insertion = D[i][j - 1] + 1; - int deletion = D[i - 1][j] + 1; - int match = D[i - 1][j - 1]; - int mismatch = D[i - 1][j - 1] + 1; - if (A.at(i - 1) == B.at(j - 1)) { - D[i][j] = std::min(insertion, std::min(deletion, match)); + for (int i = 0; i < n + 1; i++) { + // Initialize row/column 0 to 0 is necessary! + if (i == 0 || j == 0) { + D[i][j] = 0; + continue; + } + if (a.at(i - 1) == b.at(j - 1)) { + D[i][j] = D[i - 1][j - 1] + 1; } else { - D[i][j] = std::min(insertion, std::min(deletion, mismatch)); + D[i][j] = std::max(D[i - 1][j], D[i][j - 1]); } } } - return D[n][m]; } -//TEST(EditDistance, d2) { -// ASSERT_EQ(0, editDistance("ab", "ab")); -//} -//TEST(EditDistance, d1) { -// ASSERT_EQ(1, editDistance("a", "x")); +//TEST(LCS2, t1) { +// vector<int> a = { 2, 7, 5 }; +// vector<int> b = { 2, 5 }; +// ASSERT_EQ(2, lcs2(a, b)); //} // -//TEST(EditDistance, d3) { -// ASSERT_EQ(3, editDistance("short", "ports")); +//TEST(LCS2, t2) { +// vector<int> a = { 1, 9, 2, 5, 5, 5, 8, 3, 5, 11, 0, 2, 4, 1, 7, 4, 5, 9, 2, +// 4, 0, 3, 1, 5, 8, 3, 5, 9, 7, 8, 4, 5, 6, 7 }; +// vector<int> b = { 6, 3, 8, 3, 1, 8, 3, 5, 0, 9, 6, 8, 3, 5, 7, 9, 1, 4, 7, +// 9, 3, 5, 9, 0, 1, 4, 2, 7, 5, 8, 9, 3, 5, 6, 1, 6, 3, 1, 6, 7, 3 }; +// ASSERT_EQ(17, lcs2(a, b)); //} // -//TEST(EditDistance, d4) { -// ASSERT_EQ(5, editDistance("editing", "distance")); +//TEST(LCS2, t3) { +// vector<int> a = { 1, 2, 3 }; +// vector<int> b = { 3, 2, 1 }; +// ASSERT_EQ(1, lcs2(a, b)); //} int main() { - string str1; - string str2; - std::cin >> str1 >> str2; - std::cout << editDistance(str1, str2) << std::endl; - return 0; + size_t n; + std::cin >> n; + vector<int> a(n); + for (size_t i = 0; i < n; i++) { + std::cin >> a[i]; + } + + size_t m; + std::cin >> m; + vector<int> b(m); + for (size_t i = 0; i < m; i++) { + std::cin >> b[i]; + } + + std::cout << lcs2(a, b) << std::endl; } |