UVa 12467 - Secret word

The question can be solved easily in O(n*n) using naive algorithm to check the given string in its inversed string and printing the maximum matched prefix string.But it would result in TLE as the constraints are large (n<=1e6).

But it can be solved easily using KMP which would take O(n+n) time to calculate the answer.

Here process() is used to form an array(generally known as lps[]) of the given string which stores index such that if a mismatch occurs then from which previous index should the comparision be resumed.

kmpsearch() computes the maximum length matched of the given string in its inversed string which is "z" in my case.This method is mostly same as the process method() , the only difference is that kmpsearch() involves both the strings (p & q) whereas process() involves only processing the string to be searched(p).

My Code:    

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,z,a[MAX];
string p,q;

void process(){
    int i,j;
    i=0;j=-1;a[0]=-1;
    while(i<n){
        while(j>=0 && p[i]!=p[j])
            j=a[j];
        i++;j++;
        a[i]=j;
    }
}

void kmpsearch(){
    int i,j;
    i=0;j=0;
    while(i<n){
        while(j>=0 && q[i]!=p[j])
            j=a[j];
        i++;j++;
        z=max(z,j);
    }
}

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,x1=0,y1=0;
    ll ans=0;

    si(t);
    while(t--){
        clr(a,0);
        cin>>p;
        n=p.size();
        q=p;
        reverse(all(q));
        z=0;
        process();
        kmpsearch();
        rf(i,z-1,0)
            printf("%c",p[i]);
        nl;
    }

    return 0;
}