Abnormal 89's

A palindrome is a word that can be read the same way in either direction. More formally if a string is d (d > 0) characters length and the i-th character is a_i, the string is palindrome if and only if a_i equals a_(d-i+1) for 1id. For example "abcba" is palindrome while "aaab" is not.

It is known that everyone who gets to know palindromes, begin an emotional relationship with these beautiful strings. The harmony between the letters makes them artistic. But the 89's (those who entered AUT at 1389) claim they love another kind of strings. It is called alindrome. Actually an alindrome is the result of concatenation of two palindromes. For example "abacc"="aba"+"cc" is alindrome.

Now you should write a program to distinguish alindromes, palindromes and other kind of strings.

Input 

The first line contains T (T50), the number of tests. Each test that comes in a separate line contains a string to be checked. Input strings contain only lower case letters ( 'a' to 'z' ) and their length will be at most 200000.

Output 

For each test output a single word in a single line. If the input string can be made by concatenating two palindromes, output "alindrome". Otherwise if it’s a palindrome output "palindrome". In any other case print "simple". (Quotes for clarity)

Sample Input 

4
aaa
aabaa
aabaaa
abc

Sample Output 

alindrome
palindrome
alindrome
simple

---

做法 : KMP

if the string is s ... and its reverse is r....
try to find r in s+s

#include<stdio.h>
#include<string.h>
#define MaxL 400005
char A[MaxL], B[MaxL];
int P[MaxL];
void KMPTable(char *A) {
	int i, j;
	P[0] = -1, i = 1, j = -1;
	while(A[i]) {
		while(j >= 0 && A[j+1] != A[i])
			j = P[j];
		if(A[j+1] == A[i])
			j++;
		P[i++] = j;
	}
}
int KMPMatching(char A[], char B[]) {
	KMPTable(B);
	int i, j, Alen, Blen, flag = -1, match;
	Alen = strlen(A), Blen = strlen(B);
	for(i = 0, j = -1; i+(Blen-(j+1)) <= Alen; i++) {
		while(j >= 0 && B[j+1] != A[i])
			j = P[j];
		if(B[j+1] == A[i])	j++;
		if(j == Blen-1) {	
			match = i-Blen+1;
			if(match)
				return match;
			flag = 0;
			j = P[j];
			continue;
		}
	}
	return flag;
}
void Solve(char A[]) {
	int Alen = strlen(A), Blen = Alen;
	int i, j;
	for(i = 0, j = Blen-1; i < Alen; i++, j--)
		B[j] = A[i];
	B[Blen] = '\0';
	for(i = 0, j = Alen; i < Alen; i++, j++)
		A[j] = A[i];
	A[j] = '\0';
	int match = KMPMatching(A, B);
	if(match == 0 || match == Alen)
		puts("palindrome");
	else if(match == -1)
		puts("simple");
	else
		puts("alindrome");
}
int main() {
	int T;
	scanf("%d", &T);
	while(T--) {
		scanf("%s", A);
		Solve(A);
	}
    return 0;
}