Maximal Palindromic Factorization
Ali Alatabbi, Costas S. Iliopoulos, M. Sohel Rahman · 2013
Abstract. A palindrome is a symmetric string, phrase, number, or other sequence of units sequence that reads the same forward and backward. We present an algorithm for maximal palindromic factorization of a finite string by adapting an Gusfield algorithm [15] for detecting all occurrences of maximal palin-dromes in a string in linear time to the length of the given string then using the breadth first search (BFS) to find the maximal palindromic factorization set. A factorization F of s with respect to S refers to a decomposition of s such that s = si1si2 · · · siℓ where sij ∈ S and ℓ is minimum. In this context the set S is referred to as the factorization set. In this paper, we tackle the following problem. Given a string s, find the maximal palindromic factorization of s, that is a factorization of s where the factorization set is the set of all center-distinct maximal palindromes of a string s MP(s).