daily pastebin goal
14%
SHARE
TWEET

Longest Common Subsequence

keverman Feb 12th, 2018 (edited) 102 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. std::string LCS(std::string A, std::string B)
  2. {
  3.     std::string ret;
  4.     int a = A.size(), b = B.size(), L[a + 1][b + 1];
  5.     for(int i = 0; i <= a; i++) L[i][0] = 0;
  6.     for(int i = 1; i <= b; i++) L[0][i] = 0;
  7.  
  8.     for(int i = 1; i <= a; i++)
  9.         for(int j = 1; j <= b; j++)
  10.             L[i][j] = (A[i - 1] == B[j - 1] ? L[i - 1][j - 1] + 1: std::max(L[i - 1][j], L[i][j - 1]));
  11.  
  12.     while(a > 0 && b > 0)
  13.     {
  14.         if(A[a - 1] == B[b - 1])
  15.         {
  16.             ret += A[a - 1];
  17.             a--, b--;
  18.         }
  19.  
  20.         else
  21.         {
  22.             if(L[a - 1][b] > L[a][b - 1]) a--;
  23.             else                          b--;
  24.         }
  25.     }
  26.  
  27.     std::reverse(ret.begin(), ret.end());
  28.     return ret;
  29. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top