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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ2342】【SHOI2011】【双倍回文】  

2014-04-01 10:17:14|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    这道题就是noip吧里提到manacher算法的那道题....
    题目大意:给出一个字符串,求最长的双倍回文子串,双倍回文即它的前半部分后半部分和全部都是回文串。
    
    首先咱们可以知道manacher算法怎么做单个回文串了吧....那么问题就是这个双倍回文串。咱们来看看双倍回文串的条件是什么,设 当前咱们求出了 p[1]~p[i],假设咱们需要求以i为中心的双倍回文串咱们该怎么做?咱们先来回想双倍回文的定义,前半部分和后半部分和全部都是回文串,现在已经可以保证最后的了,那么目的就是求前半部分和后半部分相同,咱们可以利用对称性来做。首先 咱们假设i的最长回文的左端点为left ,那么咱们需要找到 j∈ (left+i)/2~i-1,使得 j+p[j]-1>=i,即j-i+1~j~i是一段回文串,然后由于对称性另一边也是回文串。
    其实就是需要枚举i的过程中在 [(i-p[i]+1+i)/2,i]中找到一个j使得 j+p[j]-1>=i且j 尽量地小。
   
    这个自己可以举几个例子就可以发现了~
    然后这个的话可以发现,咱们递增地枚举,咱们用 splay 以 j+p[j]-1为关键字插入,然后实际上就是找>=i的那一部分的j的最小值,然后超出的部分要删除掉。这些都可以O(nlogn)解决。
   
    然后这个方法略DT(对于P党来说),咱人懒没办法...发现帖子后面有人说 可以用并查集做,所以去搜索了一下。
    实际上咱们就是要找到 上面的 离(left+i)/2最近的满足条件的j,然后咱们可以发现这个对于固定了的 (left+i)/2,j是有单调性的!然后这个单调性是可以传递的!咱们用并查集合并这个单调性,每一个点最多合并N次,这里不能用按秩合并,所以复杂度就是O(logN),然后最多有N个点被合并,复杂度O(NlogN)的。

    这个利用单调性的方法实在是太赞了~~~

    还需要注意几点,首先就是 必然某个点会成为回文串中心当且仅当 它是‘#’,因为这里要求是个偶数回文串。
    然后 并查集的初始化的时候  根据上面那一点,如果当前是 #,则f[i]=i,否则f[i]=i+1。

  UPD:现在想一想...单独用splay是做不了的,因为区间是变化的,还需要一个关键字就是原顺序。所以需要树套树。所以这已经呵呵了。    
  UPD:关于平衡树的做法咱描述得不太清楚,不过现在网上对于这种做法的描述,感觉最详细的推荐这个:
  http://blog.csdn.net/czysjr/article/details/42110695
=========================

program bzoj2342;
const maxn=500010;
var n,r,id,ans:longint;
    a:array[0..maxn*4]of char;
    p:array[-1..maxn*4]of longint;
    f:array[0..maxn*4]of longint;

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

function find(p:longint):longint;
begin
  if f[p]=p then exit(p);
  f[p]:=find(f[p]);
  exit(f[p]);
end;

procedure init;
var i,j,l:longint;
begin
  readln(n);
  a[0]:='$';
  a[1]:='#';
  for i:=1 to n do
   begin
    read(a[i shl 1]);
    a[i shl 1 xor 1]:='#';
   end;
  fillchar(p,sizeof(p),0);
  r:=0;id:=0;
  n:=n shl 1+1;
  for i:=1 to n do
   begin
     if r>i then
       p[i]:=min(p[id*2-i],r-i)
     else
       p[i]:=1;
     while a[i+p[i]]=a[i-p[i]] do inc(p[i]);
     if (i+p[i]>r) then
      begin
        r:=i+p[i];
        id:=i;
      end;
     f[i]:=i+ord(a[i]<>'#'); 
   end;
  f[n+1]:=n;
  ans:=0;
  for i:=3 to n do
   if i and 1=1 then
    begin
     l:=(i-p[i]+1+i)shr 1;
     j:=find(l);
     while (j<i)and(j+p[j]-1<i) do
      begin
        f[j]:=find(j+1);
        j:=f[j];
      end;
     if ans<((i-j) shl 1) then
        ans:=((i-j) shl 1);
    end;
  write(ans);
end;

begin
  init;
 end.

    
  评论这张
 
阅读(141)| 评论(3)
推荐 转载

历史上的今天

评论

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

页脚

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