Skip to content

Instantly share code, notes, and snippets.

@moccaplusplus
Last active August 29, 2015 13:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save moccaplusplus/10996282 to your computer and use it in GitHub Desktop.
Save moccaplusplus/10996282 to your computer and use it in GitHub Desktop.
Manacher Algorithm Implementation
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;
}
}
@moccaplusplus
Copy link
Author

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! :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment