拓展KMP – edward

给定一串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)。

标签存档：拓展KMP