HDU3068 ( 最长回文 )

xiaoxiao2021-03-01  29

Problem : 3068 ( 最长回文 ) Judge Status : Accepted RunId : 6255711 Language : C++ Author : ssun Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta #include "stdio.h" #include "string.h" #define N 2200050 char str[N],nstr[2*N]; int rad[2*N]; int len,nlen; int manacher(){ int id, i, ans = 1; int mx = 0; // printf("%d",strlen(nstr)); for(i=1; i<nlen; i++){//$#1#2#3#3#2#1#不要用strlen(nstr)代替nlen if(mx > i) rad[i] = mx - i < rad[2*id-i] ? mx - i : rad[2*id-i]; else rad[i] = 1; for(;nstr[i+rad[i]] == nstr[i-rad[i]];rad[i]++) ; if(rad[i] + i > mx){ mx = rad[i] + i; id = i; } ans = rad[i] > ans ? rad[i] : ans; } return ans-1; } int main(){ while(scanf("%s",str)!=EOF){ int i=0; // memset(rad,0,sizeof(rad)); nstr[0] = '$'; nstr[1] = '#'; len = strlen(str); for(i=0; i<len; i++){ nstr[2*i+3] = '#'; nstr[2*i+2] = str[i]; } nstr[2*i+2] = 0; nlen = 2 * len + 2; printf("%d\n",manacher()); } return 0; } 参考 http://bbs.dlut.edu.cn/bbstcon.php?board=Competition&gid=23474对 Manacher算法的解释

其实值得一提的是这个程序的manacher()函数里面的for循环不要用strlen()函数,不然的话会超时,不用strlen函数而用nlen = 2 * len + 2的话250ms可以过

相关资源:新年快乐! python实现绚烂的烟花绽放效果
转载请注明原文地址: https://www.6miu.com/read-4200155.html

最新回复(0)