manacherLongestPalindrome function

String manacherLongestPalindrome(
  1. String s
)

Manacher's Algorithm: Finds the longest palindromic substring in O(n) time. Returns the longest palindromic substring.

Implementation

String manacherLongestPalindrome(String s) {
  if (s.isEmpty) return '';
  final t = '^#${s.split('').join('#')}#\$';
  final p = List<int>.filled(t.length, 0);
  int center = 0, right = 0, maxLen = 0, start = 0;
  for (int i = 1; i < t.length - 1; i++) {
    int mirror = 2 * center - i;
    if (right > i) p[i] = p[mirror].clamp(0, right - i);
    while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) {
      p[i]++;
    }
    if (i + p[i] > right) {
      center = i;
      right = i + p[i];
    }
    if (p[i] > maxLen) {
      maxLen = p[i];
      start = (i - maxLen) ~/ 2;
    }
  }
  return s.substring(start, start + maxLen);
}