UVA 11888 Abnormal 89s

Manacher的應用
[cpp]
#include<cstdio> 
#include<cstring> 
#include<cstdlib> 
#include<iostream> 
#include<algorithm> 
 
using namespace std; 
 
const int maxn=200100; 
 
int rad[maxn*2]; 
char str[maxn],s[maxn*2]; 
bool l[maxn],r[maxn]; 
//函數中參數說明：若原字符串是"abcd"， 
//則str為"$#a#b#c#d#@"，n為加上'#'以後的字符串長度        其中$和@的作用是哨兵 
//數組rad[]中記錄的是回文子串的半徑 
void Manacher(int rad[],char str[],int n){ 
    int i,mx=0,id; 
    for(i=1;i<n;i++){ 
        if(mx>i) rad[i]=min(rad[2*id-i],mx-i); 
        else rad[i]=0; 
        for(;str[i+rad[i]]==str[i-rad[i]];rad[i]++) 
            ; 
        rad[i]--; 
        if(mx<rad[i]+i){ 
            mx=rad[i]+i; 
            id=i; 
        } 
    } 
} 
 
int main(){ 
    int i,j,n; 
    scanf("%d",&n); 
    for(j=1;j<=n;j++){ 
        scanf("%s",&str[1]); 
        int len=strlen(&str[1]); 
        s[0]='$'; 
        for(i=1;i<=len;i++){ 
            s[2*i-1]='#'; 
            s[2*i]=str[i]; 
        } 
        s[2*len+1]='#'; 
        s[2*len+2]='@'; 
        Manacher(rad,s,2*len+2); 
        memset(l,0,sizeof(l));   //l記錄從左端點起哪些回文長度是可行的 
        memset(r,0,sizeof(r));   //r記錄從右端點起哪些回文長度是可行的 
        int vis=0; 
        int t=0; 
        for(i=1;i<=2*len;i++){ 
            if(rad[i]/2==t) 
                l[rad[i]]=1; 
            if(s[i]!='#') 
                t++; 
        } 
        t=0; 
        for(i=2*len+1;i>=1;i--){ 
            if(rad[i]/2==t) 
                r[rad[i]]=1; 
            if(s[i]!='#') 
                t++; 
        } 
        for(i=1;i<len;i++){ 
            if(l[i] && r[len-i]){ 
                vis=2; 
                break; 
            } 
        } 
        if(!vis){ 
            if(l[len]) 
                vis=1; 
        } 
        if(vis==2) 
            printf("alindrome\n"); 
        else if(vis==1) 
            printf("palindrome\n"); 
        else 
            printf("simple\n"); 
    } 
    return 0; 
}