fork download
copy 
  1. /// vn.spoj.com/problems/C11STR2/
  2.  
  3. /// Z by muoii
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define tag "spoj"
  8. #define maxn 0
  9. #define maxc 0
  10. #define len 31
  11. #define oo 1000000007
  12. #define mid ((l+r)>>1)
  13. #define meset(a,x) memset(a,x,sizeof(a))
  14. #define loop(x) for(int LoOpEr=x;LoOpEr-->0;)
  15. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  16.  
  17. int main()
  18. {
  19.     #ifdef dmdd
  20.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  21.     #endif // dmdd
  22.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  23.  
  24.     string a,b;
  25.     cin>>a>>b;
  26.     string s='$'+b+"@"+a;
  27.     int m=s.size()-1;
  28.  
  29.     vector<int> Z(s.size()+1);
  30.  
  31.     Z[1]=m;
  32.     int L=1,R=1;
  33.     for(int i=2,a,B;i<=m;i++)
  34.     {
  35.         if(R<i)
  36.         {
  37.             L=R=i;
  38.             while(R<=m && s[R]==s[R-L+1]) ++R;
  39.             R--;
  40.  
  41.             Z[i]=R-L+1;
  42.         }
  43.         else
  44.         {
  45.             a=i-L+1,B=R-i+1;
  46.  
  47.             if(Z[a]<B) Z[i]=Z[a];
  48.             else
  49.             {
  50.                 L=i;
  51.                 while(R<=m && s[R]==s[R-L+1]) ++R;
  52.                 R--;
  53.  
  54.                 Z[i]=R-L+1;
  55.             }
  56.         }
  57.     }
  58.  
  59.     for(int i=b.size()+2;i<=m;i++)
  60.         if(Z[i]==m-i+1)
  61.         {
  62.             cout<<a.substr(0,a.size()-Z[i])+b;
  63.             return 0;
  64.         }
  65.     cout<<a+b;
  66.     return 0;
  67. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
abca
cab
stdout
copy 
abcab
https://ideone.com/hcZqaw
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!