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 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 language | English |
|---|---|
| Title of host publication | Proceedings of the Prague Stringology Conference 2013, PSC 2013 |
| Pages | 70-77 |
| Number of pages | 8 |
| Publication status | Published - 2013 |
| Event | Prague Stringology Conference 2013, PSC 2013 - Prague, Czech Republic Duration: 2 Sept 2013 → 4 Sept 2013 |
Conference
| Conference | Prague Stringology Conference 2013, PSC 2013 |
|---|---|
| Country/Territory | Czech Republic |
| City | Prague |
| Period | 2/09/2013 → 4/09/2013 |
Keywords
- Factorization
- Graph search
- Palindromes