Hashing.cpp

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
using namespace std;
 
#define int long long
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>ordered_set;
#define all(x) x.begin(), x.end()
#define pb push_back
#define endl '\n';
#define yes cout << "YES\n";
#define no cout << "NO\n";
 
 
 

const int N = 5e5 + 9, p1 = 137, p2 = 277, mod1 = 1e9 + 7, mod2 = 1e9 + 9;
int n, dp[N];
pair<int, int> pw[N], ipw[N], a[N];

int bin(int x, int y, int mod) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = 1LL * ans * x % mod;
        x = 1LL * x * x % mod;
        y >>= 1;
    }
    return ans;
}


void cal() {
    pw[0] = {1, 1};
    for (int i = 1; i < N; i++) {
        pw[i].first = 1LL * pw[i - 1].first * p1 % mod1;
        pw[i].second = 1LL * pw[i - 1].second * p2 % mod2;
    }
    int ip1 = bin(p1, mod1 - 2, mod1);
    int ip2 = bin(p2, mod2 - 2, mod2);
    ipw[0] = {1, 1};
    for (int i = 1; i < N; i++) {
        ipw[i].first = 1LL * ipw[i - 1].first * ip1 % mod1;
        ipw[i].second = 1LL * ipw[i - 1].second * ip2 % mod2;
    }
}
struct H {
    pair<int, int> prefix[N];
    void build(string &s) {
        for (int i = 0; i < (int) s.size(); i++) {
            prefix[i].first = 1LL * s[i] * pw[i].first % mod1;
            if (i)prefix[i].first = 1LL * (1LL * prefix[i].first + prefix[i - 1].first) % mod1;
            prefix[i].second = 1LL * s[i] * pw[i].second % mod2;
            if (i)prefix[i].second = 1LL * (1LL * prefix[i].second + prefix[i - 1].second) % mod2;
        }
    }

    pair<int, int> get_hash(int i, int j) {
        pair<int, int> ans = {0, 0};
        ans.first = prefix[j].first;
        if (i) ans.first = 1LL * (1LL * (1LL * ans.first - prefix[i - 1].first) + mod1) % mod1;
        ans.first = 1LL * ans.first * ipw[i].first % mod1;
        ans.second = prefix[j].second;
        if (i) ans.second = 1LL * (1LL * (1LL * ans.second - prefix[i - 1].second) + mod2) % mod2;
        ans.second = 1LL * ans.second * ipw[i].second % mod2;
        return ans;
    }
}h1, h2;

bool palindrome(int i, int j){
    return h1.get_hash(i, j) == h2.get_hash(n - j - 1, n - i - 1);
}

bool is_pal[N];

int f(int l, int r){
    if(!is_pal[r])return 0;
    if(l == r) return 1;
    int &ans = dp[r];
    if(ans != -1)return ans;
    ans = 1;
    int lft = (r + l) / 2;
    if((r - l + 1) % 2)lft -= 1;
    if(is_pal[r]){
        ans += f(l, lft);
    }
    return ans;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cal();
    

    int t; cin >> t;
    while(t--) {
    // h1.build(s);
    // h2.build(rev);
    string a , b; cin >> a;
    b =  a;
    reverse(all(b));
    h1.build(a);
    h2.build(b);
    string ans;
    ans += a[0];
    int n = a.size();
    for(int i = 1; i < n; i++) {
        if(h1.get_hash(i, n - 1) == h2.get_hash(0, n - i - 1)) {
            break;
        }
        else ans += a[i];
    }

    reverse(all(ans));
    cout << a << " " << ans << endl;
}
    return 0;
}