https://codility.com/programmers/task/count_palindromic_slices
https://github.com/tpeczek/Codility/blob/master/Gamma%202011%20O(N).cs
In this problem we consider only strings consisting of lower-case English letters (a−z).
A string is a palindrome if it reads exactly the same from left to right as it does from right to left. For example, these strings are palindromes:
- aza
- abba
- abacaba
These strings are not palindromes:
- zaza
- abcd
- abacada
Given a string S of length N, a slice of S is a substring of S specified by a pair of integers (p, q), such that 0 ≤ p < q < N. A slice (p, q) of string S is palindromic if the string consisting of letters S[p], S[p+1], ..., S[q] is a palindrome. For example, in a string S = abbacada:
- slice (0, 3) is palindromic because abba is a palindrome,
- slice (6, 7) is not palindromic because da is not a palindrome,
- slice (2, 5) is not palindromic because baca is not a palindrome,
- slice (1, 2) is palindromic because bb is a palindrome.
Write a function
int solution(char *S);
that, given a string S of length N letters, returns the number of palindromic slices of S. The function should return −1 if this number is greater than 100,000,000.
For example, for string S = baababa the function should return 6, because exactly six of its slices are palindromic; namely: (0, 3), (1, 2), (2, 4), (2, 6), (3, 5), (4, 6).
Assume that:
http://codesays.com/2014/solution-to-gamma2011-count-palindromic-slices-by-codility/
- N is an integer within the range [0..20,000];
- string S consists only of lower-case letters (a−z).
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).
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
https://github.com/tpeczek/Codility/blob/master/Gamma%202011%20O(N).cs
