fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define Fast                      \
  4.   {                               \
  5.     ios_base::sync_with_stdio(0); \
  6.     cin.tie(0);                   \
  7.     cout.tie(0);                  \
  8.   }
  9. #define int long long
  10. const int N = 3e3 + 5;
  11. int dp[N][N];
  12. void sol()
  13. {
  14.   memset(dp, -1, sizeof dp);
  15.   string s, t;
  16.   cin >> s >> t;
  17.   function<int(int, int)> recur = [&](int i, int j) -> int
  18.   {
  19.     if (i == s.size() || j == t.size())
  20.       return 0;
  21.     int &ret = dp[i][j];
  22.     if (~ret)
  23.       return ret;
  24.     ret = 0;
  25.     if (s[i] == s[j])
  26.       ret = recur(i + 1, j + 1) + 1;
  27.     else
  28.     {
  29.       ret = max(ret, recur(i + 1, j));
  30.       ret = max(ret, recur(i, j + 1));
  31.     }
  32.   };
  33.   cout << recur(0, 0);
  34. }
  35. int32_t main()
  36. {
  37.   Fast;
  38.   int t = 1;
  39.   // cin >> t;
  40.   while (t--)
  41.   {
  42.     sol();
  43.   }
  44. }
Success #stdin #stdout 0.02s 74112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qLKJ14
language:
C++14 (clang 8.0)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!