Longest Palindromic Substring - Manacher's Algorithm
using System; public class PalindromeFinder { // Finds the longest palindromic substring in a given string using Manacher's Algorithm. // This algorithm achieves O(n) time complexity. public static string LongestPalindrome(string s) { if (string.IsNullOrEmpty(s)) { return ""; } /...
This C# code implements Manacher's algorithm to efficiently find the longest palindromic substring within a given string. It preprocesses the string to handle both odd and even length palindromes uniformly. The algorithm...
Manacher's algorithm solves the longest palindromic substring problem in O(n) time. It preprocesses the input string `s` into `processedS` by inserting a special character (e.g., '#') between every character and at the ends. This transformation ensures that all palindromes, regardless of their original length (odd or even), become odd-length palindromes in `processedS`, simplifying the logic. An array `p` stores the radius of the palindrome centered at each index `i` in `processedS`. The algorithm maintains `center` and `right` pointers, representing the center and rightmost boundary of the palindrome that extends furthest to the right. When processing index `i`, it uses the symmetry property: if `i` is within the current `right` boundary, its initial palindrome radius `p[i]` can be at least `min(right - i, p[mirror])`, where `mirror` is the index symmetric to `i` around `center`. Then, it attempts to expand the palindrome centered at `i` character by character. If `i + p[i]` extends beyond `right`, `center` and `right` are updated. The maximum `p[i]` found corresponds to the longest palindrome. The time complexity is O(n) because each character is compared at most a constant number of times during the expansion phase, and the `center`/`right` updates ensure forward progress. The space complexity is O(n) for storing `processedS` and the `p` array.
function LongestPalindrome(s): if s is empty or null, return "" processedS = PreprocessString(s) // Add '#' between chars and at ends n = length of processedS p = array of size n, initialized to 0 // p[i] = radius of pal...