Xue Yu

查找最长回文

2

第六章后缀树 6.4.4 查找最长回文提到了一种算法 如果字符串S的某个子串w是一个回文,则w一定也是reverse(S)的子串。例 如“issi”是“mississippi”的子串,同时它也是反转的字符串“ippississim”的子串。 根据这一点,我们可以通过寻找S和reverse(S)的最长公共子串来获得最长回文。 palindromem(S) = LCS(suffixTree(S ∪ reverse(S))) 这个方法实际上是有bug的，比如有一个字符串S =`ABXYBA`,reverse(S) = `ABYXBA`,他们的最长公共子串是`AB`或者`BA`,但这明显不是一个回文，当一个字符串包含它的某个子字符串的reverse的时候，用这个方法会有问题。这种情况的修复办法是检查子串区间,S和reverse(S)的`AB`和`BA`子串区间都是[0:2]和[4:6]，此时这并不是一个回文子串。 看另一种状况，比如 S = `ABAD`, reverse(S) = `DABA`, 他们的公共子串`ABA`的下标区间在S和reverse(S)中就是不同的，所以这个是一个回文子串.

项目名称：[Octobook](https://github.com/KrisYu/Octobook) 子标题: Octobook 相关介绍: 一个简单的[gitbook](https://www.gitbook.com)客户端，支持在线/离线阅读，搜索等公共 项目地址： https://github.com/KrisYu/Octobook