Maximal palindromic factorization

Ali Alatabbi, Costas S. Iliopoulos, M. Sohel Rahman

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

15 Citations (Scopus)


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 palindromes 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 T of s with respect to S refers to a decomposition of s such that s = si1si2... sij where sij G S and I 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 MV(s).

Original languageEnglish
Title of host publicationProceedings of the Prague Stringology Conference 2013, PSC 2013
Number of pages8
Publication statusPublished - 2013
EventPrague Stringology Conference 2013, PSC 2013 - Prague, Czech Republic
Duration: 2 Sept 20134 Sept 2013


ConferencePrague Stringology Conference 2013, PSC 2013
Country/TerritoryCzech Republic


  • Factorization
  • Graph search
  • Palindromes


Dive into the research topics of 'Maximal palindromic factorization'. Together they form a unique fingerprint.

Cite this