Finding the borders of all palindromic substrings

Revision en1, by Qualified, 2020-10-16 16:00:27

I know that using Manacher's algorithm, we can find all pairs ($$$i$$$, $$$j$$$) such that s[i $$$\dots$$$ j] is a palindrome. This article on cp-algorithms uses 2 vectors, one in which the $$$i$$$ is the center of an odd length palindrome, the other in which the $$$i$$$ is the latter of the 2 middle elements of an even length palindrome. But how do we convert this information into a vector<pair<int, int>> where the pair represents the boundaries of the palindrome substring?

Tags manacher algo, subpalindromes, #strings

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Qualified 2020-10-16 16:00:27 558 Initial revision (published)