fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define NAME "test"
  5. #define endl '\n'
  6. #define FOR(x, y, z) for(int x = y; x <= z; x++)
  7. #define FORL(x, y, z) for(int x = y; x >= z; x--)
  8.  
  9. const int N = 5e5 + 5;
  10. const int mod = 1e9 + 7;
  11. const int base = 311;
  12. int test;
  13.  
  14. string n;
  15. int Size, lo;
  16. int p1[N], p2[N];
  17. int hash1[N], hash2[N];
  18.  
  19. int get1(int l, int r)
  20. {
  21.     return ((hash1[r] - hash1[l - 1] * p1[r - l + 1]) % mod + mod) % mod;
  22. }
  23.  
  24. int get2(int l, int r)
  25. {
  26.     return ((hash2[l] - hash2[r + 1] * p2[r - l + 1]) % mod + mod) % mod;
  27. }
  28.  
  29. void solve()
  30. {
  31.     cin >> n;
  32.  
  33.     Size = n.size();
  34.     n = " " + n;
  35.  
  36.     p1[0] = 1;
  37.     FOR(i, 1, Size) p1[i] = (p1[i - 1] * base) % mod;
  38.     FORL(i, Size, 1) p2[i] = (p2[i + 1] * base) % mod;
  39.  
  40.     FOR(i, 1, Size) hash1[i] = (hash1[i - 1] * base + n[i] - 'a' + 1) % mod;
  41.     FORL(i, Size, 1) hash2[i] = (hash2[i + 1] * base + n[i] - 'a' + 1) % mod;
  42.  
  43.     FORL(i, Size, 1)
  44.     {
  45.         if (get1(i, Size) == get2(i, Size))
  46.         {
  47.             lo = i;
  48.         }
  49.     }
  50.  
  51.     FOR(i, 1, Size) cout << n[i];
  52.     FORL(i, lo - 1, 1) cout << n[i];
  53.     cout << endl;
  54.  
  55.     memset(hash1, 0, sizeof(hash1));
  56.     memset(hash2, 0, sizeof(hash2));
  57. }
  58.  
  59. signed main()
  60. {
  61.     if(fopen(NAME".inp", "r"))
  62.     {
  63.         freopen(NAME".inp","r",stdin);
  64.         freopen(NAME".out","w",stdout);
  65.     }
  66.  
  67.     //test = 1;
  68.     cin >> test;
  69.  
  70.     while (test--)
  71.     {
  72.         solve();
  73.     }
  74. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/7024Sc
language:
C++14 (gcc 8.3)
created:
1 day 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!