patternMinor
Is there an algorithm for checking if a string is a catenation of palindromes?
Viewed 0 times
catenationpalindromescheckingalgorithmfortherestring
Problem
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:
Note: the answer is trivially yes if length 1-strings are defined to be palindromes. Let's assume that this is not the case.
1. k = 1
2. Split string into k substrings (all possibilities) and check
3. k++
4. repeatNote: the answer is trivially yes if length 1-strings are defined to be palindromes. Let's assume that this is not the case.
Solution
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.
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.
Context
StackExchange Computer Science Q#9540, answer score: 8
Revisions (0)
No revisions yet.