注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Hdu3068】【manacher算法】【最长回文】  

2014-05-04 20:09:59|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:求最长回文串。
    APIO貌似有提到manacher君?
    0.0然后就看到某群君里面有某君在做这道题了,所以就跟着一起复习一下吧...
    = =其实是把manacher算法全部都忘记了。
    ps:下面的代码没有AC...因为Hdu的P党的编译器太老了,能用的字符串相关的东西貌似很少啊23333333333然后C++的咱貌似还不会用字符串...= =但觉得应该可以ac吧。

=======================

program hdu3068;
const maxn=110010;
var p,a:array[0..maxn shl 1]of longint;
    tot,r,id,n,ans:longint;
    s:char;

function min(a,b:longint):longint;
begin
  if a<b then min:=a else min:=b;
end;

function init:boolean;
var i:longint;
begin
  tot:=1;
  a[0]:=-1;
  read(s);
  while (ord(s)>=ord('a'))and
  (ord(s)<=ord('z')) do
   begin
     inc(tot);
     a[tot]:=ord(s);
     inc(tot);
     read(s);
   end;
  readln;
  id:=0;r:=0;ans:=0;
  for i:=1 to tot do
   begin
     if r>i then
       p[i]:=min(r-i,p[id shl 1-i])
     else
       p[i]:=1;
     while a[i+p[i]]=a[i-p[i]] do inc(p[i]);
     if p[i]+i>r then
      begin
        r:=p[i]+i;
        id:=i;
      end;
     if ans<p[i]-1 then ans:=p[i]-1;
   end;
  writeln(ans);
  if seekeof then init:=false
  else
  begin
  readln(s);
  init:=true;
  end;
end;

begin
  assign(input,'f.in');reset(input);
  while init do;
  close(input);
end.


  评论这张
 
阅读(35)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017