AntInLoop

Manacher's Algorithm (Longest Palindromic Substring) Code Implementations

Complete Manacher's Algorithm (Longest Palindromic Substring) code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Manacher's Algorithm (Longest Palindromic Substring) Guide · Launch Interactive Visualizer

C++ Implementation

// Manacher's Algorithm Implementation in C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <chrono>

class ManacherAlgorithm {
public:
    // Transform string to handle even-length palindromes
    static std::string transformString(const std::string& str) {
        std::string transformed = "#";
        for (char c : str) {
            transformed += c;
            transformed += "#";
        }
        return transformed;
    }
    
    // Manacher's Algorithm
    static std::vector<int> manacher(const std::string& str) {
        if (str.empty()) return {};
        
        std::string transformed = transformString(str);
        int n = transformed.length();
        std::vector<int> p(n, 0);
        
        int center = 0, right = 0;
        
        for (int i = 0; i < n; i++) {
            // Mirror position
            int mirror = 2 * center - i;
            
            if (i < right) {
                p[i] = std::min(right - i, p[mirror]);
            }
            
            // Expand palindrome centered at i
            int left = i - (p[i] + 1);
            int r = i + (p[i] + 1);
            
            while (left >= 0 && r < n && transformed[left] == transformed[r]) {
                p[i]++;
                left--;
                r++;
            }
            
            // Update center and right boundary
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
        }
        
        return p;
    }
    
    // Find all palindromes
    struct Palindrome {
        std::string text;
        int start;
        int end;
        int length;
        
        Palindrome(const std::string& t, int s, int e, int len) 
            : text(t), start(s), end(e), length(len) {}
    };
    
    static std::vector<Palindrome> findAllPalindromes(const std::string& str) {
        std::vector<int> p = manacher(str);
        std::vector<Palindrome> palindromes;
        
        for (int i = 0; i < p.size(); i++) {
            if (p[i] > 0) {
                int start = (i - p[i]) / 2;
                int length = p[i];
                std::string palindrome = str.substr(start, length);
                palindromes.emplace_back(palindrome, start, start + length - 1, length);
            }
        }
        
        return palindromes;
    }
    
    // Find longest palindrome
    static std::string findLongestPalindrome(const std::string& str) {
        std::vector<int> p = manacher(str);
        int maxLength = 0;
        int maxCenter = 0;
        
        for (int i = 0; i < p.size(); i++) {
            if (p[i] > maxLength) {
                maxLength = p[i];
                maxCenter = i;
            }
        }
        
        if (maxLength == 0) return "";
        
        int start = (maxCenter - maxLength) / 2;
        return str.substr(start, maxLength);
    }
    
    // Count all palindromes
    static int countPalindromes(const std::string& str) {
        std::vector<int> p = manacher(str);
        int count = 0;
        
        for (int length : p) {
            if (length > 0) count++;
        }
        
        return count;
    }
    
    // Find palindromes of specific length
    static std::vector<Palindrome> findPalindromesOfLength(const std::string& str, int targetLength) {
        std::vector<int> p = manacher(str);
        std::vector<Palindrome> palindromes;
        
        for (int i = 0; i < p.size(); i++) {
            if (p[i] == targetLength) {
                int start = (i - p[i]) / 2;
                std::string palindrome = str.substr(start, targetLength);
                palindromes.emplace_back(palindrome, start, start + targetLength - 1, targetLength);
            }
        }
        
        return palindromes;
    }
    
    // Check if string is palindrome
    static bool isPalindrome(const std::string& str) {
        if (str.length() <= 1) return true;
        
        std::vector<int> p = manacher(str);
        int maxLength = *std::max_element(p.begin(), p.end());
        return maxLength == str.length();
    }
    
    // Find palindromic substrings with minimum length
    static std::vector<Palindrome> findPalindromesMinLength(const std::string& str, int minLength) {
        std::vector<int> p = manacher(str);
        std::vector<Palindrome> palindromes;
        
        for (int i = 0; i < p.size(); i++) {
            if (p[i] >= minLength) {
                int start = (i - p[i]) / 2;
                int length = p[i];
                std::string palindrome = str.substr(start, length);
                palindromes.emplace_back(palindrome, start, start + length - 1, length);
            }
        }
        
        return palindromes;
    }
    
    // Performance measurement
    struct ManacherResult {
        std::vector<int> palindromeArray;
        std::string longestPalindrome;
        int palindromeCount;
        long long executionTime;
        
        ManacherResult(const std::vector<int>& p, const std::string& longest, 
                      int count, long long time) 
            : palindromeArray(p), longestPalindrome(longest), 
              palindromeCount(count), executionTime(time) {}
    };
    
    static ManacherResult manacherWithTiming(const std::string& str) {
        auto start = std::chrono::high_resolution_clock::now();
        std::vector<int> p = manacher(str);
        std::string longest = findLongestPalindrome(str);
        int count = countPalindromes(str);
        auto end = std::chrono::high_resolution_clock::now();
        
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        return ManacherResult(p, longest, count, duration.count());
    }
    
    // Performance comparison
    static void comparePerformance(const std::string& str) {
        auto start = std::chrono::high_resolution_clock::now();
        std::vector<int> p = manacher(str);
        std::string longest = findLongestPalindrome(str);
        int count = countPalindromes(str);
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        
        std::cout << "Manacher's Algorithm: " << count << " palindromes found in " 
                  << duration.count() << " μs" << std::endl;
        std::cout << "Longest palindrome: " << longest << " (length: " << longest.length() << ")" << std::endl;
    }
};

JAVA Implementation

// Manacher's Algorithm Implementation in Java

import java.util.*;

public class ManacherAlgorithm {
    // Transform string to handle even-length palindromes
    private static String transformString(String str) {
        StringBuilder sb = new StringBuilder("#");
        for (char c : str.toCharArray()) {
            sb.append(c).append("#");
        }
        return sb.toString();
    }
    
    // Manacher's Algorithm
    public static int[] manacher(String str) {
        if (str.isEmpty()) return new int[0];
        
        String transformed = transformString(str);
        int n = transformed.length();
        int[] p = new int[n];
        
        int center = 0, right = 0;
        
        for (int i = 0; i < n; i++) {
            // Mirror position
            int mirror = 2 * center - i;
            
            if (i < right) {
                p[i] = Math.min(right - i, p[mirror]);
            }
            
            // Expand palindrome centered at i
            int left = i - (p[i] + 1);
            int r = i + (p[i] + 1);
            
            while (left >= 0 && r < n && transformed.charAt(left) == transformed.charAt(r)) {
                p[i]++;
                left--;
                r++;
            }
            
            // Update center and right boundary
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
        }
        
        return p;
    }
    
    // Find all palindromes
    public static List<Map<String, Object>> findAllPalindromes(String str) {
        int[] p = manacher(str);
        List<Map<String, Object>> palindromes = new ArrayList<>();
        
        for (int i = 0; i < p.length; i++) {
            if (p[i] > 0) {
                int start = (i - p[i]) / 2;
                int length = p[i];
                String palindrome = str.substring(start, start + length);
                
                Map<String, Object> palInfo = new HashMap<>();
                palInfo.put("text", palindrome);
                palInfo.put("start", start);
                palInfo.put("end", start + length - 1);
                palInfo.put("length", length);
                palindromes.add(palInfo);
            }
        }
        
        return palindromes;
    }
    
    // Find longest palindrome
    public static String findLongestPalindrome(String str) {
        int[] p = manacher(str);
        int maxLength = 0;
        int maxCenter = 0;
        
        for (int i = 0; i < p.length; i++) {
            if (p[i] > maxLength) {
                maxLength = p[i];
                maxCenter = i;
            }
        }
        
        if (maxLength == 0) return "";
        
        int start = (maxCenter - maxLength) / 2;
        return str.substring(start, start + maxLength);
    }
    
    // Count all palindromes
    public static int countPalindromes(String str) {
        int[] p = manacher(str);
        int count = 0;
        
        for (int length : p) {
            if (length > 0) count++;
        }
        
        return count;
    }
    
    // Find palindromes of specific length
    public static List<Map<String, Object>> findPalindromesOfLength(String str, int targetLength) {
        int[] p = manacher(str);
        List<Map<String, Object>> palindromes = new ArrayList<>();
        
        for (int i = 0; i < p.length; i++) {
            if (p[i] == targetLength) {
                int start = (i - p[i]) / 2;
                String palindrome = str.substring(start, start + targetLength);
                
                Map<String, Object> palInfo = new HashMap<>();
                palInfo.put("text", palindrome);
                palInfo.put("start", start);
                palInfo.put("end", start + targetLength - 1);
                palindromes.add(palInfo);
            }
        }
        
        return palindromes;
    }
    
    // Check if string is palindrome
    public static boolean isPalindrome(String str) {
        if (str.length() <= 1) return true;
        
        int[] p = manacher(str);
        int maxLength = Arrays.stream(p).max().orElse(0);
        return maxLength == str.length();
    }
    
    // Find palindromic substrings with minimum length
    public static List<Map<String, Object>> findPalindromesMinLength(String str, int minLength) {
        int[] p = manacher(str);
        List<Map<String, Object>> palindromes = new ArrayList<>();
        
        for (int i = 0; i < p.length; i++) {
            if (p[i] >= minLength) {
                int start = (i - p[i]) / 2;
                int length = p[i];
                String palindrome = str.substring(start, start + length);
                
                Map<String, Object> palInfo = new HashMap<>();
                palInfo.put("text", palindrome);
                palInfo.put("start", start);
                palInfo.put("end", start + length - 1);
                palInfo.put("length", length);
                palindromes.add(palInfo);
            }
        }
        
        return palindromes;
    }
    
    // Performance measurement
    public static class ManacherResult {
        public int[] palindromeArray;
        public String longestPalindrome;
        public int palindromeCount;
        public long executionTime;
        
        public ManacherResult(int[] p, String longest, int count, long time) {
            this.palindromeArray = p;
            this.longestPalindrome = longest;
            this.palindromeCount = count;
            this.executionTime = time;
        }
    }
    
    public static ManacherResult manacherWithTiming(String str) {
        long startTime = System.nanoTime();
        int[] p = manacher(str);
        String longest = findLongestPalindrome(str);
        int count = countPalindromes(str);
        long endTime = System.nanoTime();
        
        return new ManacherResult(p, longest, count, endTime - startTime);
    }
    
    // Utility method for analysis
    public static Map<String, Object> manacherAnalysis(String str) {
        int[] p = manacher(str);
        String transformed = transformString(str);
        
        Map<String, Object> analysis = new HashMap<>();
        analysis.put("originalString", str);
        analysis.put("transformedString", transformed);
        analysis.put("palindromeArray", p);
        analysis.put("maxPalindromeLength", Arrays.stream(p).max().orElse(0));
        analysis.put("totalPalindromes", Arrays.stream(p).filter(length -> length > 0).count());
        
        Map<String, String> efficiency = new HashMap<>();
        efficiency.put("timeComplexity", "O(n)");
        efficiency.put("spaceComplexity", "O(n)");
        efficiency.put("comparisons", String.valueOf(str.length()));
        analysis.put("efficiency", efficiency);
        
        return analysis;
    }
}

JAVASCRIPT Implementation

// Manacher's Algorithm Implementation in JavaScript

// Transform string to handle even-length palindromes
function transformString(str) {
  return '#' + str.split('').join('#') + '#';
}

// Manacher's Algorithm
function manacher(str) {
  if (str.length === 0) return [];
  
  const transformed = transformString(str);
  const n = transformed.length;
  const p = new Array(n).fill(0);
  
  let center = 0, right = 0;
  
  for (let i = 0; i < n; i++) {
    // Mirror position
    const mirror = 2 * center - i;
    
    if (i < right) {
      p[i] = Math.min(right - i, p[mirror]);
    }
    
    // Expand palindrome centered at i
    let left = i - (p[i] + 1);
    let r = i + (p[i] + 1);
    
    while (left >= 0 && r < n && transformed[left] === transformed[r]) {
      p[i]++;
      left--;
      r++;
    }
    
    // Update center and right boundary
    if (i + p[i] > right) {
      center = i;
      right = i + p[i];
    }
  }
  
  return p;
}

// Find all palindromes
function findAllPalindromes(str) {
  const p = manacher(str);
  const transformed = transformString(str);
  const palindromes = [];
  
  for (let i = 0; i < p.length; i++) {
    if (p[i] > 0) {
      const start = Math.floor((i - p[i]) / 2);
      const length = p[i];
      const palindrome = str.substring(start, start + length);
      palindromes.push({
        text: palindrome,
        start: start,
        end: start + length - 1,
        length: length
      });
    }
  }
  
  return palindromes;
}

// Find longest palindrome
function findLongestPalindrome(str) {
  const p = manacher(str);
  let maxLength = 0;
  let maxCenter = 0;
  
  for (let i = 0; i < p.length; i++) {
    if (p[i] > maxLength) {
      maxLength = p[i];
      maxCenter = i;
    }
  }
  
  if (maxLength === 0) return "";
  
  const start = Math.floor((maxCenter - maxLength) / 2);
  return str.substring(start, start + maxLength);
}

// Count all palindromes
function countPalindromes(str) {
  const p = manacher(str);
  let count = 0;
  
  for (let i = 0; i < p.length; i++) {
    if (p[i] > 0) {
      count++;
    }
  }
  
  return count;
}

// Find palindromes of specific length
function findPalindromesOfLength(str, targetLength) {
  const p = manacher(str);
  const palindromes = [];
  
  for (let i = 0; i < p.length; i++) {
    if (p[i] === targetLength) {
      const start = Math.floor((i - p[i]) / 2);
      const palindrome = str.substring(start, start + targetLength);
      palindromes.push({
        text: palindrome,
        start: start,
        end: start + targetLength - 1
      });
    }
  }
  
  return palindromes;
}

// Check if string is palindrome
function isPalindrome(str) {
  if (str.length <= 1) return true;
  
  const p = manacher(str);
  const maxLength = Math.max(...p);
  return maxLength === str.length;
}

// Find palindromic substrings with minimum length
function findPalindromesMinLength(str, minLength) {
  const p = manacher(str);
  const palindromes = [];
  
  for (let i = 0; i < p.length; i++) {
    if (p[i] >= minLength) {
      const start = Math.floor((i - p[i]) / 2);
      const length = p[i];
      const palindrome = str.substring(start, start + length);
      palindromes.push({
        text: palindrome,
        start: start,
        end: start + length - 1,
        length: length
      });
    }
  }
  
  return palindromes;
}

// Find palindromic substrings with maximum length
function findPalindromesMaxLength(str, maxLength) {
  const p = manacher(str);
  const palindromes = [];
  
  for (let i = 0; i < p.length; i++) {
    if (p[i] > 0 && p[i] <= maxLength) {
      const start = Math.floor((i - p[i]) / 2);
      const length = p[i];
      const palindrome = str.substring(start, start + length);
      palindromes.push({
        text: palindrome,
        start: start,
        end: start + length - 1,
        length: length
      });
    }
  }
  
  return palindromes;
}

// Find overlapping palindromes
function findOverlappingPalindromes(str) {
  const p = manacher(str);
  const palindromes = [];
  
  for (let i = 0; i < p.length; i++) {
    if (p[i] > 0) {
      const start = Math.floor((i - p[i]) / 2);
      const length = p[i];
      const palindrome = str.substring(start, start + length);
      palindromes.push({
        text: palindrome,
        start: start,
        end: start + length - 1,
        length: length,
        center: i
      });
    }
  }
  
  // Find overlapping pairs
  const overlapping = [];
  for (let i = 0; i < palindromes.length; i++) {
    for (let j = i + 1; j < palindromes.length; j++) {
      const p1 = palindromes[i];
      const p2 = palindromes[j];
      
      if (p1.start <= p2.end && p2.start <= p1.end) {
        overlapping.push([p1, p2]);
      }
    }
  }
  
  return overlapping;
}

// Performance measurement
function manacherWithTiming(str) {
  const startTime = performance.now();
  const p = manacher(str);
  const longest = findLongestPalindrome(str);
  const count = countPalindromes(str);
  const endTime = performance.now();
  
  return {
    palindromeArray: p,
    longestPalindrome: longest,
    palindromeCount: count,
    executionTime: endTime - startTime
  };
}

// Utility functions
function manacherAnalysis(str) {
  const p = manacher(str);
  const transformed = transformString(str);
  
  return {
    originalString: str,
    transformedString: transformed,
    palindromeArray: p,
    maxPalindromeLength: Math.max(...p),
    totalPalindromes: p.filter(length => length > 0).length,
    efficiency: {
      timeComplexity: 'O(n)',
      spaceComplexity: 'O(n)',
      comparisons: str.length
    }
  };
}

PYTHON Implementation

# Manacher's Algorithm Implementation in Python

def transform_string(s):
    """Transform string to handle even-length palindromes"""
    return '#' + '#'.join(s) + '#'

def manacher(s):
    """Manacher's Algorithm"""
    if not s:
        return []
    
    transformed = transform_string(s)
    n = len(transformed)
    p = [0] * n
    
    center = right = 0
    
    for i in range(n):
        # Mirror position
        mirror = 2 * center - i
        
        if i < right:
            p[i] = min(right - i, p[mirror])
        
        # Expand palindrome centered at i
        left = i - (p[i] + 1)
        r = i + (p[i] + 1)
        
        while left >= 0 and r < n and transformed[left] == transformed[r]:
            p[i] += 1
            left -= 1
            r += 1
        
        # Update center and right boundary
        if i + p[i] > right:
            center = i
            right = i + p[i]
    
    return p

def find_all_palindromes(s):
    """Find all palindromes"""
    p = manacher(s)
    transformed = transform_string(s)
    palindromes = []
    
    for i in range(len(p)):
        if p[i] > 0:
            start = (i - p[i]) // 2
            length = p[i]
            palindrome = s[start:start + length]
            palindromes.append({
                'text': palindrome,
                'start': start,
                'end': start + length - 1,
                'length': length
            })
    
    return palindromes

def find_longest_palindrome(s):
    """Find longest palindrome"""
    p = manacher(s)
    max_length = 0
    max_center = 0
    
    for i in range(len(p)):
        if p[i] > max_length:
            max_length = p[i]
            max_center = i
    
    if max_length == 0:
        return ""
    
    start = (max_center - max_length) // 2
    return s[start:start + max_length]

def count_palindromes(s):
    """Count all palindromes"""
    p = manacher(s)
    count = 0
    
    for length in p:
        if length > 0:
            count += 1
    
    return count

def find_palindromes_of_length(s, target_length):
    """Find palindromes of specific length"""
    p = manacher(s)
    palindromes = []
    
    for i in range(len(p)):
        if p[i] == target_length:
            start = (i - p[i]) // 2
            palindrome = s[start:start + target_length]
            palindromes.append({
                'text': palindrome,
                'start': start,
                'end': start + target_length - 1
            })
    
    return palindromes

def is_palindrome(s):
    """Check if string is palindrome"""
    if len(s) <= 1:
        return True
    
    p = manacher(s)
    max_length = max(p)
    return max_length == len(s)

def find_palindromes_min_length(s, min_length):
    """Find palindromic substrings with minimum length"""
    p = manacher(s)
    palindromes = []
    
    for i in range(len(p)):
        if p[i] >= min_length:
            start = (i - p[i]) // 2
            length = p[i]
            palindrome = s[start:start + length]
            palindromes.append({
                'text': palindrome,
                'start': start,
                'end': start + length - 1,
                'length': length
            })
    
    return palindromes

def find_palindromes_max_length(s, max_length):
    """Find palindromic substrings with maximum length"""
    p = manacher(s)
    palindromes = []
    
    for i in range(len(p)):
        if 0 < p[i] <= max_length:
            start = (i - p[i]) // 2
            length = p[i]
            palindrome = s[start:start + length]
            palindromes.append({
                'text': palindrome,
                'start': start,
                'end': start + length - 1,
                'length': length
            })
    
    return palindromes

def find_overlapping_palindromes(s):
    """Find overlapping palindromes"""
    p = manacher(s)
    palindromes = []
    
    for i in range(len(p)):
        if p[i] > 0:
            start = (i - p[i]) // 2
            length = p[i]
            palindrome = s[start:start + length]
            palindromes.append({
                'text': palindrome,
                'start': start,
                'end': start + length - 1,
                'length': length,
                'center': i
            })
    
    # Find overlapping pairs
    overlapping = []
    for i in range(len(palindromes)):
        for j in range(i + 1, len(palindromes)):
            p1 = palindromes[i]
            p2 = palindromes[j]
            
            if p1['start'] <= p2['end'] and p2['start'] <= p1['end']:
                overlapping.append([p1, p2])
    
    return overlapping

def manacher_with_timing(s):
    """Performance measurement"""
    import time
    start_time = time.time()
    p = manacher(s)
    longest = find_longest_palindrome(s)
    count = count_palindromes(s)
    end_time = time.time()
    
    return {
        'palindrome_array': p,
        'longest_palindrome': longest,
        'palindrome_count': count,
        'execution_time': end_time - start_time
    }

def manacher_analysis(s):
    """Utility function for analysis"""
    p = manacher(s)
    transformed = transform_string(s)
    
    return {
        'original_string': s,
        'transformed_string': transformed,
        'palindrome_array': p,
        'max_palindrome_length': max(p),
        'total_palindromes': sum(1 for length in p if length > 0),
        'efficiency': {
            'time_complexity': 'O(n)',
            'space_complexity': 'O(n)',
            'comparisons': len(s)
        }
    }