51nod 1089 最长回文子串 V2（Manacher算法）

51nod 1089 最长回文子串 V2（Manacher算法）

基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题 输入N求N的阶乘的10进制表示的长度。例如6! = 720，长度为3。   Input 第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 1000) 第2 - T + 1行：每行1个数N。（1 <= N <= 10^9) Output 共T行，输出对应的阶乘的长度。 Input示例 3 4 5 6 Output示例 2 3 3初次用hash求回文串 。 #include #include #define Maxl 1000000 #define max(a,b) a>b?a:b char str1[Maxl*2]; int str2[Maxl*4],i,wz,hash_l[Maxl*2],hash_r[Maxl*2],p=29,pow[Maxl*2]={1}; void hash() { for(i=1;i<=wz;++i) pow[i]=pow[i-1]*p; for(i=wz;i>=1;--i) hash_l[i]=hash_l[i+1]*p+str2[i]; for(i=1;i<=wz;++i) hash_r[i]=hash_r[i-1]*p+str2[i]; } int main() { scanf("%s",str1); int len=strlen(str1); for(i=0;i>1; if(hash_r[i-1]-hash_r[i-mid-1]*pow[mid]==hash_l[i+1]-hash_l[i+mid+1]*pow[mid]) l=mid; else r=mid; } ans=max(ans,l); } printf("%d",ans); return 0; }

我们都在命运之湖上荡舟划桨，波浪起伏着而我们无法逃脱孤航。但是假使我们迷失了方向，波浪将指引我们穿越另一天的曙光。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。