Created
July 29, 2024 18:29
-
-
Save lsem/afd3d5cb5d6ad1bdb1c01f6ececbb288 to your computer and use it in GitHub Desktop.
lcs.cpp
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <algorithm> | |
| #include <iostream> | |
| #include <string_view> | |
| using namespace std; | |
| string_view head(string_view s) { return s.substr(0, 1); } | |
| string_view tail(string_view s) { return s.substr(1, s.size() - 1); } | |
| // longest common subsequence | |
| int lcs(string_view s1, string_view s2) { | |
| if (s1.empty() || s2.empty()) { | |
| // what is common subsequence between empty string and other? | |
| return 0; | |
| } | |
| const auto lcs1 = lcs(s1, tail(s2)); | |
| const auto lcs2 = lcs(tail(s1), s2); | |
| const auto lcs3 = lcs(tail(s1), tail(s2)); | |
| return (head(s1) == head(s2) ? 1 : 0) + std::max(lcs1, std::max(lcs2, lcs3)); | |
| } | |
| int lcs_bottom_up(string_view s1, string_view s2) { | |
| vector<vector<int>> dp_table(s1.size() + 1, vector<int>(s2.size() + 1)); | |
| for (size_t i = 0; i < s1.size(); ++i) | |
| dp_table[i][0] = 0; | |
| for (size_t i = 0; i < s2.size(); ++i) | |
| dp_table[0][i] = 0; | |
| for (size_t i = 1; i <= s1.size(); ++i) { | |
| for (size_t j = 1; j <= s2.size(); ++j) { | |
| dp_table[i][j] = | |
| (s1[i - 1] == s2[j - 1] ? 1 : 0) + | |
| std::max(dp_table[i - 1][j - 1], | |
| std::max(dp_table[i - 1][j], dp_table[i][j - 1])); | |
| } | |
| } | |
| return dp_table[s1.size()][s2.size()]; | |
| } | |
| // lcs is MJAU | |
| int main() { cout << lcs_bottom_up("XMJYAUZ", "MZJAWXU") << "\n"; } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment