fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define nmax 1000007
  5. #define mmax 3007
  6. const long long mod = 1e9 + 7;
  7. long long dp[mmax][mmax];
  8. string conv(const string &e)
  9. {
  10.     string r = "";
  11.     char c = ' ';
  12.     int n = 0;
  13.     for (char ch : e)
  14.     {
  15.         if (isalpha(ch))
  16.         {
  17.             if (n > 0) r += string(n, c);
  18.             c = ch;
  19.             n = 0;
  20.         }
  21.         else if (isdigit(ch)) n = n * 10 + (ch - '0');
  22.     }
  23.     if (n > 0) r += string(n, c);
  24.     return r;
  25. }
  26. long long solve1(const string &a, const string &b)
  27. {
  28.     long long m = a.size(), n = b.size();
  29.     for (int i = 1; i <= m; i++)
  30.     {
  31.         for (int j = 1; j <= n; j++)
  32.         {
  33.             if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
  34.             else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  35.         }
  36.     }
  37.     return dp[m][n];
  38. }
  39. long long solve2(const string &a, const string &b)
  40. {
  41.     int m = a.size(), n = b.size(), res = 0;
  42.     for (int i = 1; i <= m; i++)
  43.     {
  44.         for (int j = 1; j <= n; j++)
  45.         {
  46.             if (a[i - 1] == b[j - 1])
  47.             {
  48.                 dp[i][j] = dp[i - 1][j - 1] + 1;
  49.                 res = max((ll) res, dp[i][j]);
  50.             }
  51.         }
  52.     }
  53.     return res;
  54. }
  55. signed main()
  56. {
  57.     cin.tie(0)->sync_with_stdio(0);
  58.     if (fopen("comstr.inp", "r"))
  59.     {
  60.         freopen("comstr.inp", "r", stdin);
  61.         freopen("comstr.out", "w", stdout);
  62.     }
  63.     string s, l;
  64.     cin >> s >> l;
  65.     string x = conv(s), y = conv(l);
  66.     cout << solve1(x, y) << '\n';
  67.     cout << solve2(x, y) << '\n';
  68.     return 0;
  69. }
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0
https://ideone.com/uW4diz
language:
C++ (gcc 8.3)
created:
10 days 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!