I was Googling about a rather well-known problem, namely: the longest palindromic substring
I have found links that recommend suffix tries as a good solution to the problem.
Example SO and Algos
The approach is (as I understand it) e.g. for a string S
create Sr
(which is S
reversed) and then create a generalized suffix trie.
Then find the longest common sustring of S
and Sr
which is the path from the root to the deepest node that belongs both to S
and Sr
.
So the solution using the suffix tries approach essentially reduces to Find the longest common substring
problem.
My question is the following:
If the input string is: S = “abacdfgdcaba”
so , Sr = “abacdgfdcaba”
the longest common substring is abacd
which is NOT a palindrome.
So my question is: Is the approach of using suffix tries erroneous? Am i missunderstanding/misreading here?
相关问题
- how to split a list into a given number of sub-lis
- Generate string from integer with arbitrary base i
- Finding k smallest elements in a min heap - worst-
- binary search tree path list
- High cost encryption but less cost decryption
相关文章
- JSP String formatting Truncate
- What are the problems associated to Best First Sea
- Selecting only the first few characters in a strin
- Coin change DP solution to keep track of coins
- Python: print in two columns
- Algorithm for partially filling a polygonal mesh
- Robust polygon normal calculation
- Algorithm for maximizing coverage of rectangular a
Yes, finding longest palindrome by using LCS like algorithms is not a good way, I didn't read referenced answer carefully but this line in the answer is completely wrong:
but if you read it and you have a counter example don't worry about it (you are right in 99%), this is common mistake, But simple way is as follow:
Write down the string (
barbapapa
) as follow:#b#a#r#b#a#p#a#p#a#
, now traverse each character of this new string from left to right, check its left and right to check whether it's a palindrome center or not. This algorithm is O(n^2) in worst case and works perfectly correct. but normally will finds palindrome in O(n) (sure proving this in average case is hard). Worst case is in strings with too many long palindromes likeaaaaaa...aaaa
.But there is better approach which takes O(n) time, base of this algorithm is by Manacher. Related algorithm is more complicated than what I saw in your referenced answer. But what I offered is base idea of Manacher algorithm, with clever changes in algorithm you can skip checking all left and rights (also there are algorithms by using suffix trees).
P.S: I couldn't see your Algo link because of my internet limitations, I don't know it's correct or not.
I added my discussion with OP to clarify the algorithm:
Also using
#
is because considering palindromes of even length.After finding center of palindrome in newly created string, find related palindrom (by knowing the center and its length), then remove
#
to find out biggest palindrome.