Nbrevu

Tuenti Contest 8 (Pablo Moreno)

Jun 20th, 2011
991
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