Count of palindromes that can be obtained by concatenating equal length prefix and substrings | Function to calculate the number of palindromes ; Calculation of Z - array ; Calculation of sigma ( Z [ i ] + 1 ) ; return the count ; Given String
def countPalindrome ( S ) : NEW_LINE INDENT N = len ( S ) NEW_LINE Z = [ 0 ] * N NEW_LINE l = 0 NEW_LINE r = 0 NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT if i <= r : NEW_LINE INDENT Z [ i ] = min ( r - i + 1 , Z [ i - 1 ] ) NEW_LINE DEDENT while ( ( i + Z [ i ] ) < N and ( S [ Z [ i ] ] == S [ i + Z [ i ] ] ) ) : NEW_LINE INDENT Z [ i ] += 1 NEW_LINE DEDENT if ( ( i + Z [ i ] - 1 ) > r ) : NEW_LINE INDENT l = ir = i + Z [ i ] - 1 NEW_LINE DEDENT DEDENT sum = 0 NEW_LINE for i in range ( 0 , len ( Z ) ) : NEW_LINE INDENT sum += Z [ i ] + 1 NEW_LINE DEDENT return sum NEW_LINE DEDENT S = " abab " NEW_LINE print ( countPalindrome ( S ) ) NEW_LINE