One solution for finding the longest palindromic substring could not be understood
Refer this article on leetcode , there is a common mistake to solve the longest palindromic substring problem:
Reverse S and become S. Find the longest common substring between S and S, which must also be the longest palindromic substring.
For example:
S = "abacdfgdcaba", S = "abacdgfdcaba".
The longest common substring between S and S is "abacd". It is clear that this is the wrong palindrome.
But the next fix I couldn't figure out well. Can anyone explain this with a step by step procedure / example? Thank!
To fix this, every time we find the longest common subscript candidate, we check if the substring indices are the same as the original substring indices.
source to share
There are efficient algorithms for calculating the longest palindromic substring by modifying the original substring. For example, the following:
1) create a generalized string S1 # S2 $ that takes O (n)
1) construct a suffix array O (n) → nontrivial, but there are simple algorithms O (nlogn) and O (nlog ^ 2n)
2) construct an lcp array O (n) → trivial (there is also a trivial O (nlogn)).
3) build an RMQ data structure: build O (n) and O (1) queries -> no trivial (there are trivial constructions O (nlogn) and O (logn))
4) Iterate over each position i in the original row S1. Find the position of the complement in S2 in the generalized string. Find the longest common prefix: O (1)
In general, the mentioned approach should be changed for even and odd length palindromes. The difference is that in an odd-length palindrome, you simply enter a space when selecting indices.
This gives the solution to problem (O).
Regarding the article:
The author mentions that finding the longest common substring is not enough, since two substrings with such lcp may not be neighbors in the original string.
So we want to find two rows A and B, one of which belongs to S1 and one to S2, such that lcp (A, B) is the largest, but also A. rev (B) is in the original S1.
Hope I was clear enough.
source to share
I am stuck there, so I google for this. I understand now. Let me take the original String that the author mentioned as an example.
S = "caba', S' = "abac", so longest common substring is aba.
The sentence "we check if the substring indices are the same as the original substring indices".
1. What are substring indices?
"aba" is [1, 2, 3]
2. What are backslashes of the original indices? The reversed substring is "aba", and its original indices are also [1, 2, 3].
So, the correct answer.
And we are looking at another example.
S="abacdfgdcaba", S' = "abacdgfdcaba", so longest common substring is "abacd".
So the same process:
1. What are substring indices?
"abacd" is [0, 1, 2, 3, 4].
2. What are backslashes of the original indices? A reversed substring "abacd"
, but its original indices are also [7, 8, 9, 10, 11]
. So these two are "abacd"
not alone, the answer is wrong.
I think the proposal is a bit tricky and I think the author made it a bit difficult to understand.
I think the sentence should be changed to "To fix this, every time we find the longest common subscript candidate, we check if the substring is the same as the backsplash."
source to share