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

链接

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

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

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

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

不失一般性假设在答案中，那么肯定存在一段，其中。

显然就是我们要求的目标串。

再观察一下，会发现这个条件等价于
其中revlcp是指往前的lcp

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

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

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