daily pastebin goal
59%
SHARE
TWEET

Longest Common Substring

keverman Feb 13th, 2018 90 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.     int a = A.size(), b = B.size(), DP[a + 1][b + 1] = {0}, pos, res = 0;
  4.    
  5.     for(int i = 0; i <= a; i++)
  6.         for(int j = 0; j <= b; j++)
  7.             if(A[i - 1] == B[j - 1] && res < (DP[i][j] = DP[i - 1][j - 1] + 1))
  8.                 res = DP[i][j], pos = i - 1;
  9.    
  10.     std::string ret(res, 'x');
  11.     while(res > 0) ret[--res] = A[pos--];
  12.    
  13.     return ret;
  14. }
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