File Palindromes.h

↰ Parent directory (ADS/string)

Three classic problems on the palindromes of a sequence s of n items, and the eertree.

Definition (ADS/string/Palindromes.h)

Detailed Description

  • longestPalindromicSubstring(): the longest contiguous palindrome, by the algorithm of Manacher in :math:` Theta( n ) ` time and space. The dynamic programming of the textbook fills the table P[ i ][ j ], whether s[ i .. j ] is a palindrome, by increasing length, in :math:` Theta( n^2 ) ` time and space, and the expansion about each of the 2 n - 1 centres takes :math:` O( n^2 ) ` time and O( 1 ) space; Manacher keeps the rightmost palindrome found so far and starts each new centre from the radius of its mirror inside it, so that the right end only moves forward. The suffix tree of s and of its reverse gives the same answer in linear time with a much larger constant [see File SuffixTree.h].

  • longestPalindromicSubsequence(): the longest palindrome that is a subsequence of s: DP[ i ][ j ], its length for s[ i .. j ], is 1 if i = j, DP[ i + 1 ][ j - 1 ] + 2 if s_i = s_j, the larger of DP[ i + 1 ][ j ] and DP[ i ][ j - 1 ] otherwise, :math:` Theta( n^2 ) ` time and space, the palindrome read back from both ends. It is the longest common subsequence of s and of its reverse [see File LongestCommonSubsequence.h], so the bit-parallel and the sparse algorithms of the LCS apply to it too.

  • palindromicPartition(): the fewest palindromes into which s can be cut: D[ j ], the fewest for s[ 0 .. j ), is the least D[ i ] + 1 over the palindromes s[ i .. j ), D[ 0 ] = 0. The textbook builds the table of the palindromes first, in :math:` Theta( n^2 ) ` space; here each palindrome s[ i .. j ) relaxes D[ j ] while it is found by the expansion about its centre, the centres taken left to right, so that D[ i ] is final when it is used: :math:` O( n^2 ) ` time and O( n ) space.

  • Eertree, beyond the book, is the eertree (palindromic tree) of Rubinchik and Shur: a node per distinct nonempty palindrome (at most n of them, since a byte added at the end creates at most one new palindrome, the longest palindromic suffix), two roots of lengths -1 and 0, the edge c from v to c v c, and the suffix link of v to its longest proper palindromic suffix; add() finds the longest palindromic suffix of the new string on the links of the previous one, O( 1 ) amortized steps for a constant alphabet (the edges of a node are a short vector here, :math:` O( sigma ) ` each).

  • palindromicFactorization(), beyond the book, gives the same fewest palindromes in :math:` O( n log n ) ` time (Fici, Gagie, Karkkainen and Kempa; Rubinchik and Shur): the lengths of the palindromic suffixes of a prefix form :math:` O( log n ) ` arithmetic series, with :math:` mathit{diff}( v ) = mathit{len}( v ) - mathit{len}( mathit{link}( v ) ) ` constant along a series and the series link to the first node past it, and the best of a series at the place i is the best of the same series at :math:` i - mathit{diff}( v ) ` together with its shortest palindrome, :math:`[

    D[ i ] = 1 + min_{v} mathit{best}_i( v ) , qquad mathit{best}_i( v ) = min{ D[ i - mathit{len}( mathit{series}( v ) ) - mathit{diff}( v ) ] , mathit{best}_{i - mathit{diff}( v )}( mathit{link}( v ) ) } ,

    ` the second term only when :math:` mathit{diff}( v ) = mathit{diff}( mathit{link}( v ) ) `.

Each function of the textbook takes any sequence S with size(), operator[], an iterator constructor and the comparison of its items; the overloads on std::string also take string literals; the eertree and its factorization take bytes.

The contracts [see File Contract.h]: the result is a palindrome; the subsequence is one of s as long as the LCS of s and its reverse, and the pieces of the partition give s back (both audits), and the factorization by the eertree has as many as the partition (an audit). The functions are defined in Palindromes.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 13, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

  1. Manacher, A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string, Journal of the ACM 22(3), 346-351, 1975, doi:10.1145/321892.321896

  1. Fici, T. Gagie, J. Karkkainen, D. Kempa, A subquadratic algorithm for minimum palindromic factorization, Journal of Discrete Algorithms 28, 41-48, 2014, doi:10.1016/j.jda.2014.08.001

  1. Rubinchik, A. M. Shur, EERTREE: an efficient data structure for processing palindromes in strings, European Journal of Combinatorics 68, 249-265, 2018, doi:10.1016/j.ejc.2017.07.021

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions