分治+扩展KMP 最长回文子串 hdu 3294 Girls' research

缘起

【1】中已经给出了扩展KMP的板子, 【2】中验证了它的性能. 这里使用分治+扩展KMP给出最长回文子串的算法. 关于最长回文子串，【3】中已经给出了一种算法——manacher（马拉车算法）. 这里给出分治+扩展KMP算法.

于是我找到了 hdu 3294 来试试这种算法

这个算法显然没有马拉车来的简单，但仅仅是练习扩展KMP而已.

分析

题意很裸

有一天，sailormoon女孩非常高兴，他们打算研究回文字符串。 操作包含两个步骤：
第一步：女孩会在纸上写一个长串（只包含小写）。 例如，“abcde”，但“a”里面不是真正的'a'，这意味着如果我们定义'b'是真正的'a'，那么我们可以推断出'c'是真正的'b' ，'d'是真正的'c'......，'a'是真正的'z'。 根据这个，字符串“abcde”变为“bcdef”。
第二步：女孩会发现给定字符串中最长的回文字符串，回文字符串的长度必须等于或大于2。

输入
输入包含多个案例。
每个案例包含两个部分，一个字符和一个字符串，它们用一个空格分隔，字符表示'a'代表的字符是啥，字符串的长度不超过200000.所有输入必须是小写的。
如果字符串的长度为len，则标记为0到len-1（即索引从0开始）

输出
请按照上面两个步骤执行操作。
如果找到一个，则在一行中输出回文字符串的起始位置和结束位置，下一行输出真正的回文字符串，或输出“No solution！”。
如果有多个答案可用，请选择首次出现的字符串。

样例输入
b babd
a abcd

样例输出
0 2
aza
No solution!

限制
Time limit 1000 ms
Memory limit 32768 kB

分治+扩展KMP的算法在何林的OI论文中有详述, 这里再叙述一遍.

既然是分治, 所以我们只需要考虑跨越中线的回文子串问题（其余的交给递归即可）. 也就是下图

​ 图1

M是字符串的中线，id是回文串的中线（注意，考虑到回文串的长度可能是奇数或者偶数，所以M和id未必是索引）

根据回文串的定义不难知道蓝色的两段和黄色的两段分别都关于id镜像对称（从而两段黄色的拼接在一起一定是回文）. 注意，这里的A和M都是索引

那么如何在O(1)时间内获取到这个回文串的最长能够达到的长度呢?

我们只需要枚举A. 就知道图1中我们只需构造（其中r(L)的含义是r的逆向）

文本串	模式串
L	r(L)
r(L)	R

这两个的extend数组. 分别为 extend1和extend2. 则如果2extend1[A]>=M-A+1的话，则黄色的两段拼接在一起一定是回文串. 然后这个回文串再对外延展extend2[A], 则A对应的回文子串最长是M-A+1+2\extend2[A]

同理，对于A在M的右侧的情形

​ 图2

则和上面一样的分析, 我们需要如下的extend数组

文本串	模式串
r(R)	R
R	r(L)

令其为 extend3和extend4.

则枚举A，A对应的最长回文子串是 (M-A+1)+2extend4[A], 当然前提是2\extend3[A]>=(M-A+1)

所以综上，我们枚举A，每次枚举做出决断的耗时是O(1)， 考虑到分治，最后的时间复杂度是O(nlogn). 可能不及马拉车算法的均摊O(n), 但是稳定性好，但是编码复杂度远胜于马拉车算法. 所以要我现场写的话，肯定选择马拉车（除非测试数据变态，不然一般卡不了马拉车）

代码不写了——细节太多了，知道思想就好了

参考

【1】https://yfsyfs.github.io/2019/07/07/%E6%89%A9%E5%B1%95KMP%E9%97%AE%E9%A2%98/

【2】https://yfsyfs.github.io/2019/07/07/%E6%89%A9%E5%B1%95KMP%E7%AE%97%E6%B3%95-hdu-2594-Simpsons%E2%80%99-Hidden-Talents/

【3】https://yfsyfs.github.io/2019/07/08/Manacher%E7%AE%97%E6%B3%95-leetcode-5-%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2/