1354 - Palindrome. Again Palindrome -Timus(HASHING)

#include <bits/stdc++.h>

using namespace std;

template < int MOD >
class Zn {
    long long value;

    public:
        Zn(int value = 0) {
            this -> value = ((value % MOD) + MOD) % MOD;
        }

        Zn operator *(const Zn &other) const {
            return (this -> value * other.value) % MOD;
        }

        Zn operator +(const Zn &other) const {
            return (this -> value + other.value) % MOD;
        }

        Zn operator -() const {
            return (MOD - this -> value) % MOD;
        }

        Zn operator -(const Zn &other) const {
            return (this -> value - other.value + MOD) % MOD;
        }

        Zn operator ^(const unsigned int exp) const {
            if(exp == 0)
                return Zn(1);
            if(exp & 1)
                return (*this) * ((*this) ^ (exp - 1));
            Zn ab2 = (*this) ^ (exp >> 1);
            return ab2 * ab2;
        }

        Zn operator /(const Zn &other) const {
            return (*this) * (other ^ (unsigned int)(MOD - 2));
        }

        operator int() const {
            return this -> value;
        }
};

const int P1 = 1000000007;
const int P2 = 1000000009;

struct Hash {
    Zn<P1> rest1;
    Zn<P2> rest2;
    int Size;

    Hash() {
        rest1 = 0;
        rest2 = 0;
        Size = 0;
    }
};

const int MAX_N = 100000;
const int BASE = 253;

Zn<P1> Bases1[MAX_N + 1];
Zn<P2> Bases2[MAX_N + 1];

void init() {
    int i;
    Bases1[0] = 1;
    Bases2[0] = 1;
    for(i = 1; i <= MAX_N; ++i) {
        Bases1[i] = Bases1[i - 1] * Zn<P1>(BASE);
        Bases2[i] = Bases2[i - 1] * Zn<P2>(BASE);
    }
}

Hash append(Hash s, char l) {
    s.rest1 = s.rest1 * Zn<P1>(BASE) + Zn<P1>(l);
    s.rest2 = s.rest2 * Zn<P2>(BASE) + Zn<P2>(l);
    ++s.Size;
    return s;
}

Hash prepend(char l, Hash s) {
    s.rest1 = Zn<P1>(l) * Bases1[s.Size] + s.rest1;
    s.rest2 = Zn<P2>(l) * Bases2[s.Size] + s.rest2;
    ++s.Size;
    return s;
}

Hash join(Hash s1, Hash s2) {
    s1.rest1 = s1.rest1 * Bases1[s2.Size] + s2.rest1;
    s1.rest2 = s1.rest2 * Bases2[s2.Size] + s2.rest2;
    s1.Size += s2.Size;
    return s1;
}

bool equals(Hash s1, Hash s2) {
    return s1.rest1 == s2.rest1 && s1.rest2 == s2.rest2 && s1.Size == s2.Size;
}

Hash eraseFromEnd(Hash s, char l) {
    s.rest1 = (s.rest1 - Zn<P1>(l)) / Zn<P1>(BASE);
    s.rest2 = (s.rest2 - Zn<P2>(l)) / Zn<P2>(BASE);
    --s.Size;
    return s;
}

Hash eraseFromBeginning(char l, Hash s) {
    s.rest1 = s.rest1 - Zn<P1>(l) * Bases1[s.Size - 1];
    s.rest2 = s.rest2 - Zn<P2>(l) * Bases2[s.Size - 1];
    --s.Size;
    return s;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    init();
    string s;
    cin >> s;
    int N = s.size(), sol = N;
    Hash normal, invers;
    for(int i = N - 1; i > 0; --i) {
        normal = prepend(s[i], normal);
        invers = append(invers, s[i]);
        if(equals(invers, normal))
            sol = i;
    }
    for(int i = sol - 1; i >= 0; --i)
        s.push_back(s[i]);
    cout << s;
}