-
Notifications
You must be signed in to change notification settings - Fork 4.3k
/
ManachersAlgorithm.java
87 lines (79 loc) · 3.01 KB
/
ManachersAlgorithm.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
* An implementation of Manacher's algorithm which can be used to find/count palindromic strings in
* linear time. In particular, it finds the length of the maximal palindrome centered at each index.
*/
package com.williamfiset.algorithms.strings;
public class ManachersAlgorithm {
// Manacher's algorithm finds the length of the longest palindrome
// centered at a specific index. Since even length palindromes have
// a center in between two characters we expand the string to insert
// those centers, for example "abba" becomes "^#a#b#b#a#$" where the
// '#' sign represents the center of an even length string and '^' & '$'
// are the front and the back of the string respectively. The output
// of this function gives the diameter of each palindrome centered
// at each character in this expanded string, for instance:
// manachers("abba") -> [0, 0, 1, 0, 1, 4, 1, 0, 1, 0, 0]
public static int[] manachers(char[] str) {
char[] arr = preProcess(str);
int n = arr.length, c = 0, r = 0;
int[] p = new int[n];
for (int i = 1; i < n - 1; i++) {
int invI = 2 * c - i;
p[i] = r > i ? Math.min(r - i, p[invI]) : 0;
while (arr[i + 1 + p[i]] == arr[i - 1 - p[i]]) p[i]++;
if (i + p[i] > r) {
c = i;
r = i + p[i];
}
}
return p;
}
// Pre-process the string by injecting separator characters.
// We do this to account for even length palindromes, so we can
// assign them a unique center, for example: "abba" -> "^#a#b#b#a#$"
private static char[] preProcess(char[] str) {
char[] arr = new char[str.length * 2 + 3];
arr[0] = '^';
for (int i = 0; i < str.length; i++) {
arr[i * 2 + 1] = '#';
arr[i * 2 + 2] = str[i];
}
arr[arr.length - 2] = '#';
arr[arr.length - 1] = '$';
return arr;
}
// This method finds all the palindrome substrings found inside
// a string it uses Manacher's algorithm to find the diameter
// of each palindrome centered at each position.
public static java.util.TreeSet<String> findPalindromeSubstrings(String str) {
char[] S = str.toCharArray();
int[] centers = manachers(S);
java.util.TreeSet<String> palindromes = new java.util.TreeSet<>();
for (int i = 0; i < centers.length; i++) {
int diameter = centers[i];
if (diameter >= 1) {
// Even palindrome substring
if (i % 2 == 1) {
while (diameter > 1) {
int index = (i - 1) / 2 - diameter / 2;
palindromes.add(new String(S, index, diameter));
diameter -= 2;
}
// Odd palindrome substring
} else {
while (diameter >= 1) {
int index = (i - 2) / 2 - (diameter - 1) / 2;
palindromes.add(new String(S, index, diameter));
diameter -= 2;
}
}
}
}
return palindromes;
}
public static void main(String[] args) {
String s = "abbaabba";
// Outputs: [a, aa, abba, abbaabba, b, baab, bb, bbaabb]
System.out.println(findPalindromeSubstrings(s));
}
}