SHARE
TWEET

LCS otimizado

a guest Jan 22nd, 2015 38 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // OBS: s1.length() < s2.length()
  2. int LCS(string s1, string s2) {
  3.     vector<int> p[130];
  4.     for(int i = 0; i < s2.size() ; ++i) {
  5.         char index = s2[i];
  6.         p[index].push_back(i);
  7.     }
  8.  
  9.     vector<int> v;
  10.     v.push_back(-1);
  11.  
  12.     for(int i = 0; i < s1.size(); ++i) {
  13.         char index = s1[i];
  14.         for(int j = p[index].size() - 1 ; j >= 0 ; --j) {
  15.             int n = p[index][j];
  16.  
  17.             if (n > v.back()) v.push_back(n);
  18.             else *lower_bound(v.begin(), v.end(), n) = n;
  19.         }
  20.     }
  21.     return v.size() - 1;
  22. }
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