daily pastebin goal
29%
SHARE
TWEET

Tuenti Contest 8 (Pablo Moreno)

Nbrevu Jun 20th, 2011 720 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.         Author: Pablo Moreno Olalla
  3.         Email address: darthbrevu@yahoo.es
  4. */
  5. #include <cstdio>
  6. #include <string>
  7. #include <vector>
  8. #include <sstream>
  9. #include <iostream>
  10. #include <algorithm>
  11.  
  12. using namespace std;
  13.  
  14. //Again, this problems can be solved quite fast using dynamic programming in time N*M.
  15. //Other approaches are even faster, although they requiere complex structures to work. Considering that N*M
  16. //is a good enough time, I don't consider it to be worth in this case.
  17.  
  18. void solve(const string &a,const string &b,string &out) {
  19.         size_t s1=a.size();
  20.         size_t s2=b.size();
  21.         unsigned int maxLength=0;
  22.         size_t mlPosInA=0;
  23.         unsigned long res;
  24.         //To save space, only two columns will be used.
  25.         vector<unsigned int> v1(s1+1,0),v2(s1+1,0);
  26.         vector<unsigned int> *p1=&v1,*p2=&v2;
  27.         for (size_t j=1;j<=b.size();++j)        {
  28.                 for (size_t i=1;i<=a.size();++i) if (a[i-1]==b[j-1])    {
  29.                         res=(*p2)[i-1]+1;
  30.                         (*p1)[i]=res;
  31.                         if (res>maxLength)      {
  32.                                 maxLength=res;
  33.                                 mlPosInA=i-res;
  34.                         }
  35.                 }       else (*p1)[i]=0;
  36.                 swap(p1,p2);
  37.         }
  38.         out=a.substr(mlPosInA,maxLength);
  39. }
  40.  
  41. int main(int argc,char **argv)  {
  42.         //The first two lines are not strictly necessary, but make the code a little more handy.
  43.         if (argc>=2) freopen(argv[1],"r",stdin);
  44.         if (argc>=3) freopen(argv[2],"w",stdout);
  45.         string tmp;
  46.         string s1,s2,s3;
  47.         do      {
  48.                 getline(cin,tmp);
  49.                 istringstream iss(tmp);
  50.                 iss>>s1>>s2;
  51.                 if (iss.fail()) break;
  52.                 if (s1.size()>s2.size()) swap(s1,s2);   //Yes, this saves size too.
  53.                 solve(s1,s2,s3);
  54.                 cout<<s3<<endl;
  55.         }       while (!cin.eof());
  56.         return 0;
  57. }
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