fork(3) download
copy 
  1. #include <cstdlib>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <cstring>
  5. #include <string>
  6. #include <cstdio>
  7. using namespace std;
  8.  
  9. int* compute_help_table(const string & A,const string & B);
  10. string lcs(const string & A, const string & B);
  11. string simple_solution(const string & A, const string & B);
  12.  
  13. int main(void) {
  14.     string A,B;
  15.     cin>>A>>B;
  16.  
  17.     cout << lcs(A, B).size() << endl;
  18.  
  19.     return 0;
  20. }
  21.  
  22. string lcs(const string &A, const string &B) {
  23.     int m = A.size();
  24.     int n = B.size();
  25.  
  26.     if (m == 0 || n == 0) {
  27.         return "";
  28.     }
  29.     else if(m == 1) {
  30.         return simple_solution(A, B);
  31.     }
  32.     else if(n == 1) {
  33.         return simple_solution(B, A);
  34.     }
  35.     else {
  36.         int i = m / 2;
  37.  
  38.         string Asubstr = A.substr(i, m - i);
  39.         //reverse(Asubstr.begin(), Asubstr.end());
  40.         string Brev = B;
  41.         reverse(Brev.begin(), Brev.end());
  42.  
  43.         int* L1 = compute_help_table(A.substr(0, i), B);
  44.         int* L2 = compute_help_table(Asubstr, Brev);
  45.  
  46.         int k;
  47.         int M = -1;
  48.         for(int j = 0; j <= n; j++) {
  49.             if(M < L1[j] + L2[n-j]) {
  50.                 M = L1[j] + L2[n-j];
  51.                 k = j;
  52.             }
  53.         }
  54.  
  55.         delete [] L1;
  56.         delete [] L2;
  57.  
  58.         return lcs(A.substr(0, i), B.substr(0, k)) + lcs(A.substr(i, m - i), B.substr(k, n - k));
  59.     }
  60. }
  61.  
  62. int* compute_help_table(const string &A, const string &B) {
  63.     int m = A.size();
  64.     int n = B.size();
  65.  
  66.     int* first = new int[n+1];
  67.     int* second = new int[n+1];
  68.  
  69.     for(int i = 0; i <= n; i++) {
  70.         second[i] = 0;
  71.     }
  72.  
  73.     for(int i = 0; i < m; i++) {
  74.         for(int k = 0; k <= n; k++) {
  75.             first[k] = second[k];  
  76.         }
  77.  
  78.         for(int j = 0; j < n; j++) {
  79.             if(j == 0) {
  80.                 if (A[i] == B[j])
  81.                     second[1] = 1;
  82.             }
  83.             else {
  84.                 if(A[i] == B[j]) {
  85.                     second[j+1] = first[j] + 1;
  86.                 }
  87.                 else {
  88.                     second[j+1] = max(second[j], first[j+1]);
  89.                 }
  90.             }
  91.         }
  92.     }
  93.  
  94.     delete [] first;
  95.     return second;
  96. }
  97.  
  98. string simple_solution(const string & A, const string & B) {
  99.     int i = 0;
  100.     for(; i < B.size(); i++) {
  101.         if(B.at(i) == A.at(0))
  102.             return A;
  103.     }
  104.  
  105.     return "";
  106. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
abababab
bcbb
stdout
copy 
3
https://ideone.com/7sjCPA
language:
C++ (gcc 8.3)
created:
11 years 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!