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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【算法】【manacher算法】  

2014-03-31 22:54:56|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   这个算法是最近在noip吧看到的,感觉非常新颖所以就去学习了一下....然后现在就是一些总结及一个代码。

   首先这个算法貌似不是稀有算法...貌似有很多耶,所以直接贴百度 算法资料
   manachaer算法是用来在O(n)求出一个字符串以每一个字符为中心的最长回文长度p[],
   实际上就是O(n)求最长回文子串的东西。

   首先在每一个字符的左右插入一个 ‘#’ 比如这样一个字符串 wshjzaa ,它插入就是 #w#s#h#j#z#a#a#,然后咱们可以发现,假设原来是偶数回文串的话,在这个操作之后都会变成奇数回文串。 比如那个 aa 就变成了 #a#a#,这种统一是为了使算法能够更好的实现。当然最后求最大回文串的时候只需要加些特判弄回来即可。这个不妨碍复杂度的。

   然后就是算法了...咱们设原字符串是s,s[i]表示其中第i个字符,用 p[i]表示以 s[i]为中心往右能延伸的最大回文串的距离,实际上就是(最大回文串的长度+1)/2,
   比如 #  w  #  s  #  h  #   j  #  z    #   a   #   a   # 的 p[13]=3,p[2]=2,p[1]=1之类的。
          1   2  3  4  5  6  7  8  9 10 11 12 13 14 15
   咱们来看看这个p[]的性质。
   继续用刚才的字符串来做例子。
     #  w  #  s  #  h  #   j  #  z    #   a   #   a   # 
p  1   2  1  2  1  2  1  2  1  2   1   2   3   2   1
  1) 首先大部分博客文章都会提到一点,p[i]-1就是原字符串该处的最大回文串的长度。
  这个首先咱们可以验证一下上面的 p[],发现是正确的。
  咱们可以来证明一下:
  首先对于中心不为 '#’ 的,它们必然能延伸的最远地方就是‘#’(反设不能会发现矛盾,因为该新字符串就是以‘#’开头以‘#’结尾),然后半侧'#'的长度就是 p[i]/2,全部的就是 p[i],而总的长度为 2*p[i]-1,所以实际回文串长度为p[i]-1。
  然后对于中心为‘#’的,它们也必然能延伸到‘#’,所以除了中心,半侧延伸的‘#’应该有 (p[i]-1)/2,则总的就是 (p[i]-1)/2*2+1=p[i],所以实际字符串的长度还是2*p[i]-1-p[i]=p[i]-1。
  所以每求出一个 p[],咱们就用 p[]-1更新最长回文串答案即可。
  比如上面那个的答案就是 max(p[i])-1=3-1=2,即最长回文串是2,即aa。
  
  2)我们的算法的主要思想是,假设咱们已经求出了 p[1]~p[i-1],现在要求 p[i],怎么求?
       
  这里仔细想一下的话会发现这还是非常自然的=w=。
  设 p[j]( j ∈ [1,i-1])使得 p[j] 是 p[1]~p[i-1]中最长回文串右端点延伸最远的。(比如上面wshjzaa对于1~4的话j=4)
 
  咱们知道 以 j 为中心的最长回文串的最右端 就是 p[j]+j-1 。咱们记作 right。
  然后假设 i 在 j~right内部的话,由于 j 是回文串,所以 i 有一个关于j的对称点i' 设 p[i']+i-1不超过right,那么显然就有 p[i]=p[i'] 否则就有 p[i]=right-i+1。(这个考虑对称性即可)

  【算法】【manacher算法】 - z55250825 - z55250825

【算法】【manacher算法】 - z55250825 - z55250825
   这两种情况考虑了之后,还有一种情况就是 right<i怎么破?QAQ
   这个嘛,咱们就直接暴力扩展即可(即向左向右暴力),然后更新最右端,那么咱们可以发现,对于小于当前最长回文串右端的,咱们可以O(1)求出来,对于剩下的,咱们可以暴力求出来并且使最右端往右移,最多∑右移量为O(N)级别的,所以咱们的算法就是O(N)的。咱们可以在O(N)的时间内求出每一个字符的P[],然后就可以得到 最长回文串了。
    所以这个算法的复杂度就是 O(N)的。
    然后初始化的时候直接让 中心点为0,p[0]=0即可(这里是p党的,C++党可以直接设p[1]=1,因为第一个点为‘#’,它的扩展长度肯定为1(左边没地方扩展了))。
    写的有些凌乱...但是感觉主方法应该还是出来了吧..
     代码明天码了
      实际上很短咱会乱说?
     (下面的r代表的是最右端【开区间的】,id表示的是达到最右端的字符串的中心点,初始化为0)

   r:=0;id:=0;
   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 p[i]+i>r then
      begin
        r:=p[i]+i;
        id:=i;
      end;
   end;


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

历史上的今天

评论

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

页脚

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