fork(3) download
copy 
  1. #include<bits/stdc++.h>
  2. #define N 2000005
  3. using namespace std		;
  4. string original ;
  5. string rev  ;
  6. string medium   ;
  7. vector <int> vec (N,0)    ;
  8.  
  9. using namespace std;
  10. void z_function(){
  11.     int left  = 0   ;
  12.     int right = 0   ;
  13.     int n = medium.size()    ;
  14.     for (int i = 1; i < n; i++){
  15.  
  16.         if (i <= right)
  17.             vec[i] = min(right - i + 1, vec[i - left]) ;
  18.  
  19.         while (i + vec[i] < n  && medium[vec[i]] == medium[i + vec[i]])
  20.             vec[i]++    ;
  21.  
  22.         if (i + vec[i] -1 > right){
  23.             right = i + vec[i] - 1  ;
  24.             left = i    ;
  25.         }
  26.     }
  27. }
  28. int main(){
  29.     ios_base::sync_with_stdio(0);   cin.tie(0)  ;
  30.     while(!cin.eof()){
  31.             cin >> rev ;
  32.             original = rev;
  33.             reverse(rev.begin(), rev.end())   ;
  34.             if (original == rev){
  35.             	cout << original << "\n"	;
  36.             	continue;
  37.             }
  38.             medium = rev + original ;
  39.             z_function()   ;
  40.             int n = original.size()	;
  41.             int m = 2 * n	;
  42.            for(int i = n; i < m; i++)
  43.            		if (m - i == vec[i]){
  44.                         cout << original    ;
  45.            			for (int j  = n - vec[i] - 1; j >= 0; j--)
  46.            				cout << original[j] ;
  47.                     break;
  48.  
  49.            		}
  50.             cout << "\n"    ;
  51.             for (int i = 0; i <= m; i++)
  52.                 vec[i] = 0  ;
  53.     }
  54.     return  0;
  55. }
  56.  
Success #stdin #stdout 0s 2824KB
comments (?)
stdin
copy 
aaaa
abba
amanaplanacanal
xyz
stdout
copy 
aaaa
abba
amanaplanacanalpanama
xyzyx
https://ideone.com/GBCiY0
problem EPALIN, based on SPOJ submission 15583910 (C++ 4.3.2), 2015-11-09 20:04:35
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years ago
visibility:
secret

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!