Secret Word

#include<bits/stdc++.h>
#define sz 1000005

using namespace std;

int prefix[sz];

char rev[sz],text[sz];

int len;

void compute_prefix()
{
    int i,j=0;

    prefix[1] = 0;

    for(i=2; i<=len; i++)
    {
        while(j && rev[j+1]!=rev[i])
        {
            j = prefix[j];
        }

        if(rev[j+1]==rev[i])
        {
            j++;
        }

        prefix[i] = j;
    }
}

int KMP_match()
{
    int i,j=0;

    int mx = 0;

    for(i=1; i<=len; i++)
    {
        while(j && text[j+1]!=rev[i])
        {
            j = prefix[j];
        }

        if(text[j+1]==rev[i])
        {
            j++;
        }

        mx = max(mx,j);

        if(j==len)
        {
            j = prefix[j];
        }
    }

    return mx;
}

int main()
{
    int test,i,index;

    scanf("%d",&test);

    while(test--)
    {
        scanf("%s",rev+1);

        strcpy(text+1,rev+1);

        len = strlen(text+1);

        compute_prefix();

        reverse(rev+1,rev+len+1);

        index = KMP_match();

        for(i=index;i>0;i--)
        {
            printf("%c",text[i]);
        }

        puts("");

    }

    return 0;
}