LCS 3

#include <iostream> #include <algorithm> std::string str1,str2,str3; int dp[101][101][101]; void input_faster() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); } void input() { std::cin >> str1 >> str2 >> str3; } void solve() { for (int i = 1 ; i <= str1.size(); i++) { for (int j = 1 ; j <= str2.size(); j++) { for (int k = 1 ; k <= str3.size(); k++) { if (str1[i - 1] == str2[j - 1] && str2[j - 1] == str3[k - 1]) dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1; else dp[i][j][k] = std::max(std::max(dp[i - 1][j][k], dp[i][j - 1][k]), dp[i][j][k - 1]); } } } } void print_val() { std::cout << dp[str1.size()][str2.size()][str3.size()]; } int main() { input_faster(); input(); solve(); print_val(); return (0); }