Manacher's Algorithm — All Palindromes in O(N)

int[] manacher(String s) {
  StringBuilder t = new StringBuilder("^#");
  for (char c : s.toCharArray()) t.append(c).append('#');
  t.append('$');
  int n = t.length();
  int[] p = new int[n];
  int c = 0, r = 0;
  for (int i = 1; i < n - 1; i++) {
    if (i < r) p[i] = Math.min(r - i, p[2 * c - i]);
    while (t.charAt(i + p[i] + 1) == t.charAt(i - p[i] - 1)) p[i]++;
    if (i + p[i] > r) { c = i; r = i + p[i]; }
  }
  return p;
}