Submission

PP-P---P--

Score: 40

User: AungS8430

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.004 second

Submitted On: 2025-03-18 06:52:32

#include <bits/stdc++.h>
using namespace std;

int main(void) {
  string a, b;
  cin >> a >> b;
  vector<vector<int>> lcs(a.length() + 1, vector<int> (b.length() + 1, 0));
  for (int i = 1; i <= a.length(); i++) {
    for (int j = 1; j <= b.length(); j++) {
      if (a[i - 1] == b[j - 1]) lcs[i][j] = lcs[i - 1][j - 1] + 1;
      else lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
    }
  }
  pair<int, int> curr = {a.length(), b.length()};
  string result = "";
  while (lcs[curr.first][curr.second] != 0) {
    if (lcs[curr.first][curr.second] == max(lcs[curr.first - 1][curr.second], lcs[curr.first][curr.second - 1])) {
      if (lcs[curr.first - 1][curr.second] > lcs[curr.first][curr.second - 1]) curr.first--;
      else curr.second--;
    } else {
      result += a[curr.first - 1];
      curr.first--;
      curr.second--;
    }
  }
  reverse(result.begin(), result.end());
  cout << result << endl << lcs[a.length()][b.length()] << endl << (lcs[a.length()][b.length()] > 0.5 * a.length() && lcs[a.length()][b.length()] > 0.5 * b.length() ? "y" : "n");
  return 0;
}