Manacher的应用
[cpp]
#include?
#include?
#include?
#include?
#include?
?
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 ??????? 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 ??????????? 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 ??????????? 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;?
}?
|