Advertisement
Guest User

Untitled

a guest
Jan 31st, 2014
249
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.51 KB | None | 0 0
  1. int main(int argc, char const *argv[])
  2. {
  3.     string s;
  4.     cin>>s;
  5.     string t=s;
  6.     reverse(all(t));
  7.     string a=t+'#'+s;
  8.     //cout<<a<<"\n";
  9.     int n=sz(a);
  10.     vector<int> p(n);
  11.     int i=1,j=0;
  12.     p[0]=0;
  13.     for(int i=1;i<n;){
  14.     //  cout<<i<<" "<<j<<"\n";
  15.         if(a[i]==a[j]){
  16.             p[i]=j+1;
  17.             ++i;
  18.             ++j;
  19.         }
  20.         else{
  21.             if(j>0)j=p[j-1];
  22.             else{
  23.                 p[i]=0;
  24.                 ++i;
  25.             }
  26.         }
  27.     }
  28.     int l=sz(s)-p[n-1];
  29.     //cout<<p[n-1]<<"\n";
  30.     cout<<s;
  31.     int  co=0;
  32.     while(co<l){
  33.         cout<<s[l-co-1];
  34.         ++co;
  35.     }
  36.     cout<<"\n";
  37.     return 0;
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement