Count palindromic characteristics of a String | Python program which counts different palindromic characteristics of a string . ; function which checks whether a substr [ i . . j ] of a given is a palindrome or not . ; P [ i , j ] = True if substr [ i . . j ] is palindrome , else False ; palindrome of single length ; palindrome of length 2 ; Palindromes of length more then 2. This loop is similar to Matrix Chain Multiplication . We start with a gap of length 2 and fill P table in a way that gap between starting and ending indexes increases one by one by outer loop . ; Pick starting point for current gap ; Set ending point ; If current string is palindrome ; function which recursively counts if a str [ i . . j ] is a k - palindromic or not . ; terminating condition for a which is a k - palindrome . ; terminating condition for a which is not a k - palindrome . ; increases the counter for the if it is a k - palindrome . ; mid is middle pointer of the str [ i ... j ] . ; if length of which is ( j - i + 1 ) is odd than we have to subtract one from mid else if even then no change . ; if the is k - palindrome then we check if it is a ( k + 1 ) - palindrome or not by just sending any of one half of the to the Count_k_Palindrome def . ; Finding all palindromic substrings of given string ; counting k - palindromes for each and every sub of given string . . ; Output the number of K - palindromic substrings of a given string . ; Driver code
MAX_STR_LEN = 1000 ; NEW_LINE P = [ [ 0 for x in range ( MAX_STR_LEN ) ] for y in range ( MAX_STR_LEN ) ] ; NEW_LINE for i in range ( 0 , MAX_STR_LEN ) : NEW_LINE INDENT for j in range ( 0 , MAX_STR_LEN ) : NEW_LINE INDENT P [ i ] [ j ] = False ; NEW_LINE DEDENT DEDENT Kpal = [ 0 ] * MAX_STR_LEN ; NEW_LINE def checkSubStrPal ( str , n ) : NEW_LINE INDENT global P , Kpal , MAX_STR_LEN ; NEW_LINE for i in range ( 0 , MAX_STR_LEN ) : NEW_LINE INDENT for j in range ( 0 , MAX_STR_LEN ) : NEW_LINE INDENT P [ i ] [ j ] = False ; NEW_LINE DEDENT Kpal [ i ] = 0 ; NEW_LINE DEDENT for i in range ( 0 , n ) : NEW_LINE INDENT P [ i ] [ i ] = True ; NEW_LINE DEDENT for i in range ( 0 , n - 1 ) : NEW_LINE INDENT if ( str [ i ] == str [ i + 1 ] ) : NEW_LINE INDENT P [ i ] [ i + 1 ] = True ; NEW_LINE DEDENT DEDENT for gap in range ( 2 , n ) : NEW_LINE INDENT for i in range ( 0 , n - gap ) : NEW_LINE INDENT j = gap + i ; NEW_LINE if ( str [ i ] == str [ j ] and P [ i + 1 ] [ j - 1 ] ) : NEW_LINE INDENT P [ i ] [ j ] = True ; NEW_LINE DEDENT DEDENT DEDENT DEDENT def countKPalindromes ( i , j , k ) : NEW_LINE INDENT global Kpal , P ; NEW_LINE if ( i == j ) : NEW_LINE INDENT Kpal [ k ] = Kpal [ k ] + 1 ; NEW_LINE return ; NEW_LINE DEDENT if ( P [ i ] [ j ] == False ) : NEW_LINE INDENT return ; NEW_LINE DEDENT Kpal [ k ] = Kpal [ k ] + 1 ; NEW_LINE mid = int ( ( i + j ) / 2 ) ; NEW_LINE if ( ( j - i + 1 ) % 2 == 1 ) : NEW_LINE INDENT mid = mid - 1 ; NEW_LINE DEDENT countKPalindromes ( i , mid , k + 1 ) ; NEW_LINE DEDENT def printKPalindromes ( s ) : NEW_LINE INDENT global P , Kpal , MAX_STR_LEN ; NEW_LINE n = len ( s ) ; NEW_LINE checkSubStrPal ( s , n ) ; NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT for j in range ( 0 , n - i ) : NEW_LINE INDENT countKPalindromes ( j , j + i , 1 ) ; NEW_LINE DEDENT DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT print ( Kpal [ i ] , end = " ▁ " ) ; NEW_LINE DEDENT print ( ) ; NEW_LINE DEDENT s = " abacaba " ; NEW_LINE printKPalindromes ( s ) ; NEW_LINE