Advertisement
Guest User

Untitled

a guest
Dec 10th, 2016
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cstring>
  4.  
  5. using namespace std;
  6.  
  7. ifstream in("palindrom.in");
  8. ofstream out("palindrom.out");
  9.  
  10. const int lMax = 200005;
  11. const int MOD = 2999999;
  12. const int base = 97;
  13.  
  14. char s[lMax];
  15. int n;
  16. int hashSt[lMax];
  17. int hashDr[lMax];
  18. int basePow[lMax];
  19.  
  20. void citire()
  21. {
  22.     in >> (s + 1);
  23.     n = strlen(s + 1) + 1;
  24. }
  25.  
  26. int GetHashSt(int st, int dr)
  27. {
  28.     long long ret = 1LL * hashSt[dr] - ((1LL * hashSt[st - 1] * basePow[dr - st + 1]) % MOD);
  29.     while(ret < 0)
  30.         ret += MOD;
  31.     ret %= MOD;
  32.     return ret;
  33. }
  34. int GetHashDr(int st, int dr)
  35. {
  36.     long long ret = 1LL * hashDr[st] - ((1LL * hashDr[dr + 1] * basePow[dr - st + 1]) % MOD);
  37.     while(ret < 0)
  38.         ret += MOD;
  39.     ret %= MOD;
  40.     return ret;
  41. }
  42.  
  43. inline bool palindrom(int st, int dr)
  44. {
  45.     return (GetHashSt(st, dr) == GetHashDr(st, dr));
  46. }
  47.  
  48. void Code()
  49. {
  50.     for(int i = 1; i < n; ++i)
  51.         hashSt[i] = (hashSt[i-1] * base + s[i]) % MOD;
  52.     for(int i = n - 1; i >= 1; --i)
  53.         hashDr[i] = (hashDr[i + 1] * base + s[i]) % MOD;
  54. }
  55.  
  56. void SetBasePow()
  57. {
  58.     basePow[0] = 1;
  59.     for(int i = 1; i <= n; ++i)
  60.         basePow[i] = (basePow[i - 1] * base) % MOD;
  61. }
  62.  
  63. void rezolvare()
  64. {
  65.     Code();
  66.     SetBasePow();
  67.     int rasp = n - 1;
  68.     for(int i = 1; i < n - 1; ++i)
  69.     {
  70.         if(palindrom(i, n - 1))
  71.         {
  72.             rasp = i;
  73.             break;
  74.         }
  75.     }
  76.     out << s + 1;
  77.     for(int i = rasp - 1; i >= 1; --i)
  78.         out << s[i];
  79. }
  80.  
  81. int main()
  82. {
  83.     citire();
  84.     rezolvare();
  85.  
  86.     return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement