扩展KMP(除草)
2014-09-06 10:26:23| 分类:
总结
| 标签:
|举报
|字号大中小 订阅
这个月似乎只做了一点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
所以应该大概就是这样了吧……虽然我没有去写
感觉很好写的样子。当然如果理解错了求轻喷
评论这张
转发至微博
转发至微博
评论