The main idea is a combination of dynamic programming and (as others have said already) computing maximum length of palindrome with center in a given letter.
What we really want to calculate is radius of the longest palindrome, not the length.
The radius is simply length/2
or (length - 1)/2
(for odd-length palindromes).
After computing palindrome radius pr
at given position i
we use already computed radiuses to find palindromes in range [
i - pr ; i
]
. This lets us (because palindromes are, well, palindromes) skip further computation of radiuses
for range [
i ; i + pr
]
.
While we search in range [
i - pr ; i
]
, there are four basic cases for each position i - k
(where k
is in 1,2,... pr
):
- no palindrome (
radius = 0
) at i - k
(this means radius = 0
at i + k
, too)
- inner palindrome, which means it fits in range
(this means radius
at i + k
is the same as at i - k
)
- outer palindrome, which means it doesn't fit in range
(this means radius
at i + k
is cut down to fit in range, i.e because i + k + radius > i + pr
we reduce radius
to pr - k
)
- sticky palindrome, which means
i + k + radius = i + pr
(in that case we need to search for potentially bigger radius at i + k
)
Full, detailed explanation would be rather long. What about some code samples? :)
I've found C++ implementation of this algorithm by Polish teacher, mgr Jerzy Wa?aszek.
I've translated comments to english, added some other comments and simplified it a bit to be easier to catch the main part.
Take a look here.
Note: in case of problems understanding why this is O(n)
, try to look this way:
after finding radius (let's call it r
) at some position, we need to iterate over r
elements back, but as a result we can skip computation for r
elements forward. Therefore, total number of iterated elements stays the same.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…