首页 > 代码库 > hdu3068最长回文(Manacher算法)
hdu3068最长回文(Manacher算法)
简单来说这是个很水的东西。有点dp的思想吧。推荐两个博客，很详细。
http://blog.csdn.net/xingyeyongheng/article/details/9310555
http://blog.csdn.net/ggggiqnypgjg/article/details/6645824
然后以为随便学点然后去复习，结果……呵呵。什么鬼数据，两行之间用空行隔开……没看到一直wa半节课……
hdu3068最长回文
var s1,s2:ansistring; s:array[0..1000000]of char; p:array[0..1000000]of longint; max,ans,mid,i,len:longint; ch:char; flag:boolean;function min(x,y:longint):longint;begin if x<y then min:=x else min:=y;end;begin while not eof do begin readln(s1); readln(s2); len:=length(s1); fillchar(p,sizeof(p),0); s[0]:=‘$‘; s[1]:=‘#‘; for i:=1 to len do begin s[i*2]:=s1[i]; s[i*2+1]:=‘#‘; end; len:=len*2+2; s[len]:=‘#‘; mid:=0; max:=0; ans:=1; for i:=1 to len do begin if max>i then p[i]:=min(p[mid*2-i],max-i) else p[i]:=1; while s[i+p[i]]=s[i-p[i]] do inc(p[i]); if p[i]+i>max then begin max:=p[i]+i; mid:=i; end; if ans<p[i] then ans:=p[i]; end; writeln(ans-1); end;end.
简单来说就是判断是否被前面的覆盖到，如果有，根据对称性可以可得一个长度（min=(p[mid<<1-i]，max-i))，如果没有就长度为1，然后再根据这个长度扩展，顺便更新下最大值。
这渣状态……！！
hdu3068最长回文(Manacher算法)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。