Question: https://codility.com/demo/take-sample-test/count_palindromic_slices
Question Name: CountPalindromicSlices
This task is based on the longest palindromic substring question, which has a good solution naming Manacher’s algorithm. Some explanation about the algorithm could be found here (English) and here (Chinese).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | def palindrome_substring(str): ''' Input: string Attention: the input string will be extended. For example, original string abc would be converted into #a#b#c#. Output: array, to say palindrome_len. palindrome_len[i] records the half width (include the element in position i) of palindrome substring, which centers in position i. Method: Manacher's algorithm Time complexity: O(n) ''' str = "#" + "#".join(str) + "#" # Convert the original string so # that, every palindrome substring # in the new string has odd number # of elements. palindrome_len = [0] * len(str) # Store the half width (include the # center point) of the longest # palindrome substring with index # being the substring's center. # palindrome_len[i]-1 means the full # length of palindrome substring in # the original string. bound = 0 # Record the first positin, that the previous computed # palindrome substrings chould NOT achieve. center = 0 # Record the center position of the substring, which # is corresponding to "bound". for index in xrange(len(str)): if bound > index: # Part of current substring has already been compared. # For point "index", 2*center-index is the point # symmetrical to the points "center". palindrome_len[index] = min( palindrome_len[2*center-index], bound-index ) else: # None of current substring has been compared. palindrome_len[index] = 1 # Compare the uncompared elements one by one. while index-palindrome_len[index] >= 0 and index+palindrome_len[index] < len(str) and str[index-palindrome_len[index]] == str[index+palindrome_len[index]]: palindrome_len[index] += 1 if bound < palindrome_len[index] + index: # The bound has been extended. center = index bound = palindrome_len[index] + index return palindrome_len def solution(S): # With center point i, if the longest palindrome substring # has length of j, the number of palindrome substrings, # with the same center, is j//2. count = sum([ (length-1)/2 for length in palindrome_substring(S) if length>2 ]) if count > 100000000: return -1 else: return count |
Hey Sheng ,
I was really stuck with this one , however your mention of Manacher’s algorithm showed me the light and I thank you for that . My solution is slightly different than yours. I count the palindrome slices when palindrome length of index is calculated.
Here i my code . I am not sure how to use your tags so I am pasting the result URL.
https://codility.com/demo/results/demoEW2MFB-JXT/
I experienced the same stuck, until I noticed Manacher’s algorithm. That is why I posted all my solution online, so that you do not need to stuck at the same point and nowhere to find the right direction.
To post code, please read the “Guideline for Comments” in the right column. Thanks!