Last active
August 29, 2015 13:59
-
-
Save moccaplusplus/10996282 to your computer and use it in GitHub Desktop.
Manacher Algorithm Implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class ManacherAlgorithmImpl { | |
private int mLongestPalindromeLength; | |
private int mLongestPalindromeStart = -1; | |
public void findLongestPalindrome(String string) { | |
final int strlen = string.length(); | |
if (strlen == 0) { | |
mLongestPalindromeStart = -1; | |
mLongestPalindromeLength = 0; | |
return; | |
} | |
final int helperLength = 2 * strlen - 1; | |
final int[] helper = new int[helperLength]; | |
helper[mLongestPalindromeStart = 0] = mLongestPalindromeLength = 1; | |
int lastIndex = 0; | |
int lastMax = 0; | |
for (int i = 1; i < helperLength - mLongestPalindromeLength; i++) { | |
final int base = i / 2; | |
final int mod = i % 2; | |
int radius, offset; | |
if (i < lastMax) { | |
radius = Math.min(helper[2 * lastIndex - i], lastMax - i); | |
offset = (radius + 1 - mod) / 2; | |
} | |
else { | |
offset = radius = 1 - mod; | |
} | |
final int offsetLimit = Math.min(base + 1, strlen - base - mod); | |
while (offset < offsetLimit && | |
string.charAt(base - offset) == string.charAt( | |
base + offset + mod)) { | |
radius += 2; | |
offset++; | |
} | |
if ((helper[i] = radius) > mLongestPalindromeLength) { | |
mLongestPalindromeStart = base + mod - radius / 2; | |
mLongestPalindromeLength = radius; | |
} | |
if ((radius += i) > lastMax) { | |
lastIndex = i; | |
lastMax = radius; | |
} | |
} | |
} | |
public int getLongestPalindromeLength() { | |
return mLongestPalindromeLength; | |
} | |
public int getLongestPalindromeStart() { | |
return mLongestPalindromeStart; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This is my implementation of Manacher's algortihm in Java. I think it's one of the most concise and easiest you could find on the Internet. All variables have meaningful names so it can be easy to follow the code. It also does not allocate the helper string (as most implentations found on the Internet do), but only one additional array - e.g. track of already computed values.
Enjoy! :)