【BZOJ2342】双倍回文（manacher，并查集）

题意：

思路：From http://blog.sina.com.cn/s/blog_8d5d2f04010196bh.html

首先我可以看出：

（1）我们找到的串的本身也是一个回文串（显然）

（2）这个回文串的长度一定是偶数（显然）

（3）左右两个串一定也是偶数长度的回文串（显然）

那么我们先用manacher处理出以每个字符为中心的回文串长度

由于我们所需处理的这些串的长度都为偶数，所以这些串的中心都在manacher时的那些填充字符上（显然）

那么我们就先枚举大串的中心i,设左边小串的中心为j

那么j+rad[j]>=i (rad[]为manacher中处理出的数组)

由于左边一定是回文串，那么rad[j]就应该要覆盖到i（不然怎么保证左边是回文串），而如果左边得到保证，那么右边也一定符合条件（对称）

所以我们就只需求出满足条件的最左侧的j

然后我们对j也有一个枚举范围，那就是在i的回文串范围内，并且还在i-rad[i]/2 ~ i 之间，不然不够

这样我们就可以初步得出一个枚举算法，那就是对于每个i，在一定范围内枚举j，找最优解

据说这个算法是可过的，但是复杂度。。。。似乎不是太乐观

于是需要优化

该优化其实也是显然的

如果我们曾枚举过一个j，它不能覆盖到当前枚举的i(也就是j+rad[j]

那么这个j，用一定不能覆盖到i+1（显然）

也就是说这个j在之后的计算中都没有用了，我们就不需要枚举了

这样我们就可以在枚举j的时候一段一段的跳，以降低复杂度

而实现这个过程，我们可以用并查集

每次都将没用的j的父亲指向j+1，然后跳到getfather（j+1）

这样就轻松完成了分段跳这个优化

最后在分析一下复杂度

（1）manacher O（n）

（2）并查集 O（nα（n））

（3）每个点最多被删n次 O（n）

（4）每个点最多被利用一次 O（n）

（5）每个点最多被枚举一次 O（n）

这个复杂度真的是怎么算怎么舒心，而且代码很好实现

 var f,p:array[..]of longint;

     a:array[..]of char;

     len,i,n,mx,id,ans,j:longint;

     ch:ansistring;

 function min(x,y:longint):longint;

 begin

  if x<y then exit(x);

  exit(y);

 end;

 function max(x,y:longint):longint;

 begin

  if x>y then exit(x);

  exit(y);

 end;

 function find(k:longint):longint;

 begin

  if f[k]<>k then f[k]:=find(f[k]);

  find:=f[k];

 end;

 begin

  assign(input,'bzoj2342.in'); reset(input);

  assign(output,'bzoj2342.out'); rewrite(output);

  readln(len);

  readln(ch);

  n:=; a[]:='@'; a[]:='#';

  for i:= to len do

  begin

   inc(n); a[n]:=ch[i];

   inc(n); a[n]:='#';

  end;

  inc(n); a[n]:='$';

  mx:=; id:=;

  for i:= to n- do

  begin

   if mx>i then p[i]:=min(p[id*-i],mx-i)

    else p[i]:=;

   while a[i-p[i]]=a[i+p[i]] do inc(p[i]);

   if p[i]+i>mx then

   begin

    mx:=p[i]+i;

    id:=i;

   end;

  end;

  for i:= to n- do

   if a[i]='#' then f[i]:=i

    else f[i]:=i+;

  i:=; j:=;

  repeat

   i:=i+;

   if i>n then break;

   j:=find(max(i-p[i] div ,));

   while (j<i)and(j+p[j]<i) do

   begin

    f[j]:=find(j+);

    j:=f[j];

   end;

   if j<i then ans:=max(ans,(i-j)*);

  until i>n;

  writeln(ans);

  close(input);

  close(output);

 end.

巴特西

【BZOJ2342】双倍回文（manacher，并查集）

最新文章

热门文章