tests/aoj/lcs.longest_common_subsequence.test.cpp

View this file on GitHub
Last update: 2020-10-29 22:46:53+01:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C"

#include "../../code/dynamicProgramming/lcs.cc"

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  int tc;
  cin >> tc;
  while(tc--) {
      string s1, s2;
      cin >> s1 >> s2;
      cout << lcs(s1, s2) << endl;
  }
}

#line 1 "tests/aoj/lcs.longest_common_subsequence.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C"

#line 1 "code/template.cc"
// this line is here for a reason
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define endl '\n'
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
template <typename T>
bool ckmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <typename T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, true : false; }
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout if (DEBUG) cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#line 2 "code/dynamicProgramming/lcs.cc"
int lcs(const string& s, const string& t) {
  int n = SZ(s), m = SZ(t);
  vvi dp(n + 1, vi(m + 1, 0));
  dp[n - 1][m - 1] = s[n - 1] == t[m - 1];
  for (int i = n - 2; ~i; --i)
    dp[i][m - 1] = s[i] == t[m - 1] ? 1 : dp[i + 1][m - 1];
  for (int i = m - 2; ~i; --i)
    dp[n - 1][i] = s[n - 1] == t[i] ? 1 : dp[n - 1][i + 1];
  for (int i = n - 2; ~i; --i)
    for (int j = m - 2; ~j; --j)
      dp[i][j] = max({dp[i + 1][j + 1] + (s[i] == t[j]),
                      dp[i + 1][j], dp[i][j + 1]});
  return dp[0][0];
}
#line 4 "tests/aoj/lcs.longest_common_subsequence.test.cpp"

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  int tc;
  cin >> tc;
  while(tc--) {
      string s1, s2;
      cin >> s1 >> s2;
      cout << lcs(s1, s2) << endl;
  }
}