string - 最长回文子串和后缀trie

Question

我在谷歌上搜索了一个众所周知的问题，即:the longest palindromic substring
我发现推荐后缀尝试的链接是解决问题的好方法。
示例 SO和 Algos
该方法是(据我所知)例如对于字符串 S 创建 Sr (这是 S 的反转)，然后创建一个通用后缀特里。
然后找到S和Sr的最长公共(public)sustring，即从根节点到同时属于S和的最深节点的路径>高级。
因此，使用后缀尝试方法的解决方案实质上简化为查找最长公共(public)子串问题。
我的问题如下:
如果输入字符串是:S = “abacdfgdcaba” 所以，Sr = “abacdgfdcaba” 最长公共(public)子串是 abacd 即 不是回文。
所以我的问题是:使用后缀尝试的方法是否错误？我在这里误解/误读了吗？

Answer 1

是的，使用类似 LCS 的算法找到最长回文不是一个好方法，我没有仔细阅读引用答案，但答案中的这一行是完全错误的:

So the longest contained palindrome within a string is exactly the longest common substring of this string and its reverse

但是如果你阅读它并且你有一个反例不要担心它(你是对的 99％)，这是常见的错误，但简单的方法如下:

写下字符串(barbapapa)如下:#b#a#r#b#a#p#a#p#a#，现在遍历每个字符这个新字符串从左到右，检查它的左右，以检查它是否是回文中心。这个算法在最坏的情况下是 O(n^2) 并且完全正确。但通常会在 O(n) 中找到回文(确保在一般情况下很难证明这一点)。最坏的情况是字符串中有太多长回文，例如 aaaaaa...aaaa。

但是有更好的方法需要 O(n) 的时间，这个算法的基础是 Manacher .相关算法比我在您引用的答案中看到的更复杂。但我提供的是Manacher算法的基本思想，通过巧妙的算法变化，你可以跳过检查所有的左和右(也有使用后缀树的算法)。

---

P.S:由于我的网络限制，我看不到您的 Algo 链接，我不知道它是否正确。

我添加了与 OP 的讨论以阐明算法:

let test it with barbapapa-> #b#a#r#b#a#p#a#p#a#, start from first #
there is no left so it's center of palindrome with length 1.
Now "b",has # in left and # in right, but there isn't another left to match with right 
so it's a center of palindrome with length 3.
let skip other parts to arrive to first "p":
first left and right is # second left and right is "a", third left and
right is # but forth left and right are not equal so it's center of palindrome
of length 7 #a#p#a# is palindrome but b#a#p#a#p is not 
Now let see first "a" after first "p" you have, #a#p#a#p#a# as palindrome and this "a" 
is center of this palindrome with length 11 if you calculate all other palindromes 
length of all of them are smaller than 11

同时使用#是因为考虑到偶数长度的回文。

在新创建的字符串中找到回文的中心后，找到相关的回文(通过知道中心和长度)，然后删除#找出最大的回文。