3
$\begingroup$

Given a string $S$, I want to count the number of distinct palindromic substrings of $S$. I know the basic $o(n^2)$ approach to do so. But I want to find a better approach for strings that can be very large (of the order of $10^5$).

So I want a more efficient algorithm.

Example:

Say $S=xyx$, then the palindromic counter must return $3$ as answer, as S has three palindromic substrings: $\{x,xyx,y\}$.

$\endgroup$
0

2 Answers 2

1
$\begingroup$

You can get a table of the largest palindrome centered at each position using Manacher's algorithm in $O(n)$ time. Then create a set of palindromes (e.g. using a min heap), initially empty. Iterate over the table, adding the longest palindrome centered at each position to the set. When adding a palindrome to the set, if successful, remove the first and last characters and repeat until the string is empty or a previously-added palindrome is found.

This runs in time $O(n \log p)$, where $p$ is the palindrome count.

$\endgroup$
2
  • $\begingroup$ Could you please provide an algo or a code or so?I will be very thankful $\endgroup$ Dec 15, 2013 at 19:07
  • 1
    $\begingroup$ Here is the algorithm. 1. Create table using Manacher's algorithm 2. For each entry in the table, add the corresponding palindrome to the set, using the method specified. $\endgroup$
    – augurar
    Dec 16, 2013 at 6:37
0
$\begingroup$

Every 1-character substring is a palindrome -- as the OP already pointed out in the example. Also, every repeated character is a length-2 palindrome, e.g. $xx$ in $axxb$.

Use the set of 1-character and 2-character palindromes as your initial set. Then, for each palindrome in the set, try to extend it by 1 character left and 1 character right and check if that is still a palindrome. This happens if the characters to the left and right of an existing palindrome are equal. If they are equal, add the new palindrome to the set and try to add 2 more characters. If the step did not form a new palindrome, stop and try the next element in the existing set.

In the worst case this is still $o(n^2)$, which would happen, for example, if the string is a single character repeated $n$ times. In the best case this is $o(n)$ since palindromes are quite rare and most attempts at extending from a 1 or 2-character palindrome will end after a constant number of steps. The average case performance will depend a lot on the expected density of palindromes in the string.

$\endgroup$
3
  • $\begingroup$ R u sure the palindromic count will not contain duplicates.? I mean one substring will be counted one time.Could you please provide me a piece of code to do so? $\endgroup$ Dec 10, 2013 at 9:49
  • $\begingroup$ Yes, the palindrome count will contain duplicates. But determining whether you think $xyxyx$ contains the palindrome $xyx$ once or twice is up to you. If you don't want to count things twice, you will have to remove duplicates afterwards. $\endgroup$
    – Carl
    Dec 10, 2013 at 9:54
  • 1
    $\begingroup$ How to maintain this that i had encountered this string earlier or not?Wont it make the algorithm O(n^2) again.? $\endgroup$ Dec 10, 2013 at 9:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .