最長的迴文子串和後綴trie

Question

我是一個相當知名的問題谷歌搜索，即：the longest palindromic substring
我發現建議後綴嘗試作爲一個很好的解決方案的鏈接問題。
例子SO和Algos
該方法（據我所知）例如爲一個字符串S創建Sr（這是S反轉），然後創建一個通用後綴trie。
然後找到S和Sr這個最長的常見懸索，它是從根到最深節點的路徑，它屬於S和Sr。
因此，使用後綴嘗試方法的解決方案基本上減少到Find the longest common substring問題。
我的問題是：
如果輸入字符串是：S = 「abacdfgdcaba」如此，Sr = 「abacdgfdcaba」最長的公共子是abacd這是不是迴文。
所以我的問題是：使用後綴的方法嘗試錯誤？我在這裏誤解/誤讀嗎？

Answer 1

是，通過LCS算法一樣尋找最長的迴文是不是一個好辦法，我沒仔細看參考答案，但此行的答案是完全錯誤的：

所以中的最長的迴文所含一個字符串，正是這個字符串的最長公共子和其反向

，但如果你讀它，你有一個反例不必擔心它（你是對的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 

而且使用#是因爲考慮偶數長度的迴文。

找到新創建的字符串中的迴文中心後，找到相關的迴文（知道中心和長度），然後刪除#找出最大的迴文。