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)
}
}