[ZOJ 3199 Longest Repeated Substring] 分治、扩展KMP

链接

给定一串S,令S = *xx* (其中*为通配符)
问这个x最长的长度能是多少。

以前用罗穗骞论文的方法按后缀数组枚举长度做的。但是那个需要ST表,空间是O(n lg n)。最近从叉姐那里学会了新姿势,可以用分治的思想做,只要O(n)的空间。

具体想法是每次把字符串分成两半,分别算两边的答案。

对于跨越中间边界的,设中点为S_{mid},那么枚举答案的长度L,然后因为他跨越边界,那么一定包含S_{mid}
因为答案长度为L,那么要么S_{mid + L}在答案中,要么S_{mid - L}在答案中。

不失一般性假设S_{mid + L}在答案中,那么肯定存在一段S_{i..i+L-1} = S_{j..j+L-1},其中i \leq mid \leq i + L - 1, j \leq mid + L \leq j + L - 1

显然S_{i..i+L-1}就是我们要求的目标串。

再观察一下,会发现这个条件等价于lcp(mid, mid+L) + revlcp(mid, mid + L) - 1 \geq L
其中revlcp是指往前的lcp

最终发现,对于跨越的情况,我们只要求得lcp(mid, x)和revlcp(mid, x)的函数值即可。而这个显然可以通过拓展KMP处理出来,具体做法就是令T = S_{mid .. n} + S_{1..n},对T求拓展KMP,再对边界取一下min,反的可以转化成正的求解。

至此,这题得到了解决。
时间复杂度O(n lg n)。
空间复杂度O(n)。

代码:https://gist.github.com/edwardmjm/2b88d649ced1d7ce9a99

[ZOJ 3199 Longest Repeated Substring] 分治、扩展KMP》上有1条评论

发表评论

电子邮件地址不会被公开。