fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. struct TLSTValue {
  7.     int len;
  8.     int cnt;
  9. };
  10.  
  11.  
  12. void update(TLSTValue& v, const TLSTValue& u) {
  13.     if (u.cnt == 0) {
  14.         return;
  15.     }
  16.     if (u.len > v.len) {
  17.         v.len = u.len;
  18.         v.cnt = u.cnt;
  19.     } else if (u.len == v.len) {
  20.         v.cnt += u.cnt;
  21.     }
  22. }
  23.  
  24. int main(int /* argc */, char** /* argv */)
  25. {
  26.     string a, b;
  27.     while (cin >> a >> b) {
  28.         int n = a.size();
  29.         int m = b.size();
  30.  
  31.         vector<vector<int>> nxt(n, vector<int>(m));
  32.         for (int j = 0; j < m; ++j) {
  33.             int lst = n;
  34.             for (int i = n - 1; i >= 0; --i) {
  35.                 if (a[i] == b[j]) {
  36.                     lst = i;
  37.                 }
  38.                 nxt[i][j] = lst;
  39.             }
  40.         }
  41.  
  42.         vector<vector<TLSTValue>> f(n + 1, vector<TLSTValue>(m + 1, {0, 0}));
  43.         f[0][0]= {0, 1};
  44.         TLSTValue ans = {0, 0};
  45.         for (int i = 0; i <= n; ++i) {
  46.             unordered_set<char> st;
  47.             for (int j = 0; j <= m; ++j) {
  48.                 update(ans, f[i][j]);
  49.                 if (j) {
  50.                     update(f[i][j], f[i][j - 1]);
  51.                 }
  52.                 if (st.count(b[j])) {
  53.                     continue;
  54.                 }
  55.                 st.insert(b[j]);
  56.                 if (i < n && j < m && f[i][j].cnt && nxt[i][j] < n) {
  57.                     update(f[nxt[i][j] + 1][j + 1], {f[i][j].len + 1, f[i][j].cnt});
  58.                 }
  59.             }
  60.         }
  61.         cout << a << " and " << b << ": length = " << ans.len << ", count = " << ans.cnt << endl;
  62.     }
  63.  
  64.     cerr << "Time execute: " << clock() / (double)CLOCKS_PER_SEC << " sec" << endl;
  65.     return 0;
  66. }
  67.  
Success #stdin #stdout #stderr 0s 15240KB
comments ()
stdin
copy 
ABC AB
BCAB ABC
A AAA
AAA A
AAAB ABBB
ABBB AAAB
stdout
copy 
ABC and AB: length = 2, count = 1
BCAB and ABC: length = 2, count = 2
A and AAA: length = 1, count = 1
AAA and A: length = 1, count = 1
AAAB and ABBB: length = 2, count = 1
ABBB and AAAB: length = 2, count = 1
stderr
copy 
Time execute: 0.002938 sec
https://ideone.com/f0QpHK
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

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!