Parallelization of Manacher's Algorithm for the Longest Palindromic Substring

The Longest Palindromic Substring (LPS) problem is a classic and fundamental task in string processing with broad applications in bioinformatics, natural language processing, data security, and compression. Manacher's algorithm is the most efficient sequential solution, achieving linear time O(n); however, for very large inputs, its execution can still be time-consuming in modern high-performance computing (HPC) environments. In this work, we first implement the sequential Manacher algorithm and evaluate it on a supercomputing platform: the results confirm the expected linear behavior, yet also indicate that merely using multi-core hardware without effective parallelization is insufficient. We then survey major prior parallel approaches for palindrome-related problems and, based on this study, design and implement a parallel variant of Manacher's algorithm using the Message Passing Interface (MPI). Our approach distributes the input across processes and merges local results with minima