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

ydc的博客

 
 
 

日志

 
 

扩展KMP(除草)  

2014-09-06 10:26:23|  分类: 总结 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    这个月似乎只做了一点sgu的水题……所以就没写过什么东西了
    倒是今天看了一下扩展KMP,感觉自己终于从火星回来了

    扩展KMP解决的是这么两类问题:
    一、给定串A,对于每个i,求最大的L使得A[1~L]=A[i,i+L-1]
    二、给定串A、B,对于每个i,求最大的L使得B[1~L]=A[i,i+L-1]

    对于这两类问题,似乎经常出现,比如今年NOI2014 day2 T1
    当时我在考场上的做法是这样的,对于每个i,求出i~n与原串的最长公共前缀,那么我们要做的是个区间+1的操作,只需要采用差分的方法即可O(n),但是前面那一步我采用的是二分+hash的算法得到。
    本来二分+自然溢出的hash是可过的,但是因为在省选集训的时候我被长郡某人出题时坑了,所以那次不敢写自然溢出,于是用了pair<int,int>分别对10^9+7和10^9+9取模,然后挂了30分
    事实上这题就是裸的扩展KMP了233

    个人理解来看,扩展KMP就是和manacher一模一样的搞法
    假设next[i]为所求
    我们令R为max{i+next[i]-1},id为得到R的决策
    我们只要类似于manacher一样,如果R<i就爆枚,否则初值为next[i-id],从这里开始爆枚
    时间复杂度分析同manacher,事实上next就是manacher的rad

    所以应该大概就是这样了吧……虽然我没有去写
    感觉很好写的样子。当然如果理解错了求轻喷
  评论这张
 
阅读(292)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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