Number of Palindromic Slices in a string with O(N) complexity

Question

def solution(S):
    total = 0
    i = 1
    while i <= len(S):
        for j in range(0, len(S) - i + 1):
            if is_p(S[ j: j + i]):
                total += 1
        i += 1
    return total

def is_p(S):
    if len(S) == 1:
        return False
    elif S == S[::-1]:
        return True
    else:
        return False

I am writing a function to count the number of Palindromic Slices(with length bigger than 1) in a string. The above code is in poor time complexity. Can someone help me to improve it and make it O(N) complexity?

Edit: It is not duplicate since the other question is about finding the longest Palindromic Slices

Possible duplicate of [Counting palindromic substrings in O(n)](https://stackoverflow.com/questions/3647453/counting-palindromic-substrings-in-on) — ScottMcC, May 31 '18 at 09:34
It's a duplicate because, once you have the longest palindrome centered at some location, you instantly know how many (shorter) palindromes can be found centered there -- every centered substring of a palindrome is a palindrome. — k_ssb, May 31 '18 at 10:06

Deepak Tatyaji Ahire · Answer 1 · 2018-05-31T17:40:07.400

0

This can be done in linear time using suffix trees:

1) For constant sized alphabet we can build suffix trees using Ukkonen's Algorithm in O(n).

2) For given string S, build a generalized suffix tree of S#S' where S' is reverse of string S and # is delimiting character.

3) Now in this suffix tree, for every suffix i in S, look for lowest common ancestor of (2n-i+1) suffix is S'.

4) count for all such suffixes in the tree to get total count of all palindromes.

edited May 31 '18 at 17:40

answered May 31 '18 at 10:04

Deepak Tatyaji Ahire

4,883
2
13
35

Can you write some code to accompany each step of the answer? – zvone May 31 '18 at 10:25

k_ssb · Answer 2 · 2018-05-31T10:43:11.400

Apply Manacher's Algorithm, also described by the multiple answers to this question.

That gives you the length of the longest palindrome centered at every location (centered at a character for odd-length, or centered between characters for even-length). You can use this to easily calculate the number of palindromes. Note that every palindrome must be centered somewhere, so it must be a substring (or equal to) the longest palindrome centered there.

So consider the string ababcdcbaa. By Manacher's Algorithm, you know that the maximal length palindrome centered at the d has length 7: abcdcba. By the properties of palindromes, you immediately know that bcdcb and cdc and d are also palindromes centered at d. In fact there are floor((k+1)/2) palindromes centered at a location, if you know that the longest palindrome centered there has length k.

So you sum the results of Manacher's Algorithm to get your count of all palindromes. If you want to only count palindromes of length > 1, you just need to subtract the number of length-1 palindromes, which is just n, the length of your string.

Number of Palindromic Slices in a string with O(N) complexity

2 Answers2