If the input is 'abba' then the possible palindromes are a, b, b, a, bb, abba.
I understand that determining if string is palindrome is easy. It would be like:
public static boolean isPalindrome(String str) {
int len = str.length();
for(int i=0; i<len/2; i++) {
if(str.charAt(i)!=str.charAt(len-i-1) {
return false;
}
return true;
}
But what is the efficient way of finding palindrome substrings?
O(n)
, using Manacher's algorithm.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
):
radius = 0
) at i - k
radius = 0
at i + k
, too)radius
at i + k
is the same as at i - k
)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
)i + k + radius = i + pr
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.