範例程式碼 uva11475
//uva11475
#include<stdio.h>
#include<string.h>
#define MaxL 100005
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;
Alen = strlen(A), Blen = strlen(B);
for(i = 0, j = -1; i < Alen; i++) {
while(j >= 0 && B[j + 1] != A[i])
j = P[j];
if(B[j + 1] == A[i])
j++;
}
return j;
}
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';
int tail = KMPMatching(A, B);
for(i = Blen - 1; i > tail; i--)
printf("%c", B[i]);
printf("%s\n", B);
}
int main() {
while(scanf("%s", A) == 1)
Solve(A);
return 0;
}