Problem link
Why does my following solution get WA. I used kmp prefix function to compute the prefix of the given string and its reverse,pi2[] and pi1[] respectively.

Then I computed the longest prefix and suffix of the string which are palindromes. If the rest of the string except the palindrome prefix or suffix is also a palindrome I output it as an "alindrome". I handled two special cases for checking "palindrome" with length 1 and other "palindrome"s. All other strings are "simple".

Please help me with some test cases or pointing out any flaw in my reasoning or code. Code follows.

#include <stdio.h>
#include <string.h>
 
#define MAX 200005
 
int pi1[MAX],pi2[MAX],m;
 
void pre1(char P[])
{
    int i,k=m;
    pi1[m-1]=m;
 
    for(i=m-2;i>=0;i--)
    {
        while(k!=m && P[k-1]!=P[i])
            k=pi1[k];
 
        if(P[k-1]==P[i]) k--;
        pi1[i]=k;
    }
}
 
void pre2(char P[])
{
    int i,k=-1;
    pi2[0]=-1;
 
    for(i=1;i<m;i++)
    {
        while(k>=0 && P[k+1]!=P[i])
            k=pi2[k];
 
        if(P[k+1]==P[i]) k++;
        pi2[i]=k;
    }
}
 
int main()
{
    int t,i,k;
    char str[MAX];
 
    scanf("%d",&t);
 
    while(t--)
    {
        scanf("%s",str);
        m=strlen(str);
 
        pre1(str);
        int p=m;
        int f=1;
        for(i=0;i<m;i++)
        {
            while(p!=m && str[p-1]!=str[i])
                p=pi1[p];
 
            if(str[p-1]==str[i]) p--;
            if(i && str[i]!=str[i-1]) f=0;
        }
 
        if(f==1 && m>1)
        {
            printf("alindrome\n");
            continue;
        }
 
        if(p==0)
        {
            printf("palindrome\n");
            continue;
        }
 
        pre2(str);
        int r=-1;
        for(i=m-1;i>=0;i--)
        {
            while(r>=0 && str[r+1]!=str[i])
                r=pi2[r];
 
            if(str[r+1]==str[i]) r++;
        }
 
        for(i=p-1;i>=0;i--)
            if(str[i]!=str[p-i-1])
                break;
 
        if(i==-1)
        {
            printf("alindrome\n");
            continue;
        }
 
        for(i=r+1;i<m;i++)
            if(str[i]!=str[m-1-i+r+1])
                break;
 
        if(i==m)
        {
            printf("alindrome\n");
            continue;
        }
 
        printf("simple\n");
    }
 
    return 0;
}