Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Is there a linear-time algorithm to check that a sequence of characters is a concatenation of palindromes? The only thing that comes to my mind is the naive solution:

1. k = 1
2. Split string into k substrings (all possibilities) and check
3. k++
4. repeat

Note: the answer is trivially yes if length 1-strings are defined to be palindromes. Let's assume that this is not the case.

share|improve this question
11  
If you're allowing trivial palindromes of length 1 (e.g. the string "a" is a palindrome) then all strings are concatenations of palindromes. –  Matt Lewis Feb 6 '13 at 11:59
    
Is it useful, or an exercise? –  Jan Hudec Feb 6 '13 at 12:06
    
@MattLewis You can try to minimize the number of palindromes. Jan, why? Sounds like a nice exercise in dynamic programming. –  Pål GD Feb 6 '13 at 12:10
1  
@Haile No. Disjoint palindromes only. –  saadtaame Feb 8 '13 at 15:07
1  
Norvig did extensive work on Palindromes. You may be interested in this page: norvig.com/palindrome.html –  robowolverine Apr 22 '13 at 18:06

3 Answers 3

Assuming you want disjoint palindromes, this is known as the PALSTAR problem, and there is a linear time algorithm by Zvi Galil and Joel Seiferas. A Linear-Time On-Line Recognition Algorithm for ``Palstar'.

You can find an explanation of the algorithm in the book here: Text Algorithms (look at linked page and the preceding pages).

If you are ok with a quadratic time algorithm, straight-forward dynamic programming seems to work.

Given a string $s[1,\dots n]$, we maintain an array telling us whether $s[1,\dots j]$ can be decomposed into palindromes.

We also maintain an 2D table which tells us whether $s[i, \dots j]$ is a palindrome or not. This we can construct in $O(n^2)$ time by choosing a center and moving two pointers outwards, checking for palindromes with that center. Do this for each possible center: $\Theta(n)$ centers, each taking $O(n)$ time.

Now, you can check $s[1, \dots j+1]$ whether can be decomposed into palindromes, by checking for each $1 \le i \le j-1$ whether $s[1,\dots i]$ can be decomposed, and if $s[i+1,\dots, j+1]$ is a palindrome (using the above 2D table). This yields a $\Theta(n^2)$ time and $\Theta(n^2)$ space algorithm.

The space usage can be brought down to $O(n)$, if you use Manacher's on-line algorithm to compute whether $s[i+1,\dots j+1]$ is a palindrome (as $i$ goes from $j-1$ to $1$), basically getting rid of the 2D table.

share|improve this answer
    
This is similar to my algorithm, I just didn't explain the preprocessing part to leave it as exercise to OP, but I don't know why no one was care about my algorithm :) –  user742 Apr 28 '13 at 19:53
    
@SaeedAmiri: Have you read the first part of my answer which mentions linear time? How is it similar? btw, OP changed the question to ask for a linear time algorithm, which makes your answer, and the latter half of my answer irrelevant. I did not delete that part from my answer, because I wanted to mention Manacher's algorithm which makes the dynamic programming algorithm only use O(n) space (and gets rid of the preprocessing step), and it might still be relevant to other folks who happen to come across this question –  Aryabhata Apr 28 '13 at 22:30
    
Don't take it series, it's just kidding, I like your answers in general, I think there is a problem with my English writing, because OP didn't understand my solution, and it was out of my mood to draw it by picture. But good point OP changed his question recently, and may be there is a solution similar to Manacher's algorithm (but really is not easy). –  user742 Apr 28 '13 at 22:45
1  
@SaeedAmiri: I see, no worries then :-) –  Aryabhata Apr 28 '13 at 23:39

If overlapping is allowed, it can be done in linear time (in the size of the input string).

Some definitions

Let's define the concept of maximal palindrome:

A maximal palindrome of radius k of a string S is a substring S' such that

  • starting from the centre, S' reads the same k characters in both directions
  • but not for k+1 characters
  • k > 1 (so a single character is not a palindrome)

for example, if S = banana, then S' = anana is a maximal palindrome of radius 2.

A maximal palindrome is a maximal palindrome of radius k for some k.

For example, if S = banana, "ana", "anana", are all its maximal palindromes.

Using maximal palindromes

Now, if we could locate all maximal palindromes of a string, it would be simple to check if the whole string is a concatenation of palindromes.

Take S = abbaccazayaz. Its maximal palindromes are:

  • abba, centered between position 2 and 3, radius = 2
  • acca, centered between position 5 and 6, radius = 2
  • zayaz, centered in position 10, radius = 2

so "abba" spans over [1..4], "acca" spans over [4..7], "zayaz" spans over [8..12]. Since the concatenation of this three palindromes (overlapping is permitted?) spans over the whole string, it follows that "abbaccazayaz" is concatenation of palindromes.

Computing maximal palindromes in linear time

Now, it turns out that we can locate all maximal palindromes of a string S in linear time! *

The idea is to use a suffix tree for S equipped with constant-time lowest common ancestor queries.

So we can check if a string S of length m is a concatenation of palindromes in O(n) time.

* Gusfield, Dan (1997), "9.2 Finding all maximal palindromes in linear time", Algorithms on Strings, Trees, and Sequences

share|improve this answer
    
Assuming overlapping palindromes are allowed and that we're looking for the smallest palindrome sequence, I don't see why this should return the smallest one (I don't have a counter-example though). If we are checking if it is possible with palindromes of radius at least $k$, then it is indeed useful. Also, nana is not a palindrome, I suppose you meant anana instead. –  Khaur Feb 6 '13 at 13:13
    
Edited the "anana" thing, thank you. Also, OP does not ask for a minimal palindromes sequence: given that a single char is not a palindrome, we just have to decide if the input string is a concatenation of palindromes or not. –  Haile Feb 6 '13 at 13:26
1  
Single characters are palindromes (albeit uninteresting ones). If you assume they're not, then you're solving the second problem I mention for $k=1$. On a complexity note, after you compute all maximal palindromes, you still have to check they span the whole sequence, which IIRC takes loglinear time in the number of palindromes (which can be almost as high as the length of the sequence in pathological cases). Anyway I think you should emphasize more that you assume overlapping is allowed, as it is not such an obvious assumption. –  Khaur Feb 6 '13 at 13:46
1  
@Khaur It only takes loglinear time if the intervals are not sorted. In this case they probably are. –  Yuval Filmus Feb 6 '13 at 17:55
1  
In the comments to the question, the OP explicitly adds that overlapping palindromes are not allowed. So this solution in present form is not what the OP is looking for. I think that this solution can be modified to solve the non-overlapping case as well, with some thought and atmost quadratic complexity. But I haven't given it much thought. –  Paresh Feb 10 '13 at 10:21

Suppose Palindrome[][] is an array and Palindrome(i,j) is a function which checks, whether substring from i to j is palindrome and returns 1 if is palindrome or returns infinity if is not palindrome, and you looking for smallest number of partitions, create it bottom up:

$$Palindrome[i][i] = 1.$$ $$\forall 0\le i < j < n : Palindrome[i][j] = \min\{Palindrome(i,j), \min_{i\le k<j} \{Palindrome[i,k] + Palindrome[i+1,k]\}\}$$

You should fill $O(n^2)$ cells and each cell takes at most $O(n)$ so algorithm is $O(n^3)$, with a little modification (preprocessing) you can improve it to $O(n^2)$, Also finding this partition is not hard.

share|improve this answer
    
Can you illustrate with an example? Say: abbaaccaabba. –  saadtaame Feb 8 '13 at 15:40
    
@saadtaame, OK, here is not possible to create a table (in cs.stackexchange), or I couldn't find a way to do this, I'll do this in somewhere and I'll put the image here later. but for now you try to understand it yourself, start from substrings of length 1, then check palindroms of length 2, .... and so on. –  user742 Feb 11 '13 at 9:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.