UVA 11888 / Hashing using ULL

/***
 created: 2022-06-19-01.10.38
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define ull unsigned long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

ull p[200005];
ull hash1[200005];
ull rhash1[200005];
ull base=307;

void power()
{
    p[0]=1;
    for(int i=1;i<=200003;i++)
    {
        p[i]=p[i-1]*base;
    }
}

void hashing(string a)
{
    hash1[0]=0;
    for(int i=1; i<=a.size(); i++)
    {
        hash1[i]=(hash1[i-1]*base+a[i-1]);
    }

    rhash1[a.size()+1]=0;
    for(int i=a.size(); i>=1;i--)
    {
        rhash1[i]=(rhash1[i+1]*base + a[i-1]);
    }
}

ull forwardhash(ll l,ll r)
{
    return (hash1[r] - (hash1[l-1] * p[r-l+1]));
}

ull backwardhash(ll l,ll r)
{
    return (rhash1[l] - (rhash1[r+1] * p[r-l+1]));
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    power();

    test
    {
        string a;

        cin>>a;

        hashing(a);

        ll n,m,i,j,k,l=0;

        n=a.size();

        for(i=0;i<n-1;i++)
        {
            ull h1=forwardhash(1,i+1);
            ull h2=backwardhash(1,i+1);

            ull h3=forwardhash(i+2,n);
            ull h4=backwardhash(i+2,n);

            if(h1==h2 && h3==h4)
            {
                l=1;
                break;
            }
        }

        if(l)
        {
            cout<<"alindrome"<<nl;
        }
        else
        {
            ull h1=forwardhash(1,n);
            ull h2=backwardhash(1,n);

            if(h1==h2) cout<<"palindrome"<<nl;
            else cout<<"simple"<<nl;
        }
    }

    get_lost_idiot;
}