Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <cstring>
- using namespace std;
- ifstream in("palindrom.in");
- ofstream out("palindrom.out");
- const int lMax = 200005;
- const int MOD = 2999999;
- const int base = 97;
- char s[lMax];
- int n;
- int hashSt[lMax];
- int hashDr[lMax];
- int basePow[lMax];
- void citire()
- {
- in >> (s + 1);
- n = strlen(s + 1) + 1;
- }
- int GetHashSt(int st, int dr)
- {
- long long ret = 1LL * hashSt[dr] - ((1LL * hashSt[st - 1] * basePow[dr - st + 1]) % MOD);
- while(ret < 0)
- ret += MOD;
- ret %= MOD;
- return ret;
- }
- int GetHashDr(int st, int dr)
- {
- long long ret = 1LL * hashDr[st] - ((1LL * hashDr[dr + 1] * basePow[dr - st + 1]) % MOD);
- while(ret < 0)
- ret += MOD;
- ret %= MOD;
- return ret;
- }
- inline bool palindrom(int st, int dr)
- {
- return (GetHashSt(st, dr) == GetHashDr(st, dr));
- }
- void Code()
- {
- for(int i = 1; i < n; ++i)
- hashSt[i] = (hashSt[i-1] * base + s[i]) % MOD;
- for(int i = n - 1; i >= 1; --i)
- hashDr[i] = (hashDr[i + 1] * base + s[i]) % MOD;
- }
- void SetBasePow()
- {
- basePow[0] = 1;
- for(int i = 1; i <= n; ++i)
- basePow[i] = (basePow[i - 1] * base) % MOD;
- }
- void rezolvare()
- {
- Code();
- SetBasePow();
- int rasp = n - 1;
- for(int i = 1; i < n - 1; ++i)
- {
- if(palindrom(i, n - 1))
- {
- rasp = i;
- break;
- }
- }
- out << s + 1;
- for(int i = rasp - 1; i >= 1; --i)
- out << s[i];
- }
- int main()
- {
- citire();
- rezolvare();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement