human
Count All Palindrome Sub | Returns total number of palindrome substring of length greater then equal to 2.
creat empty 2 - D matrix that counts all palindrome substring . dp [ i ] [ j ] stores counts of palindromic substrings in st [ i . . j ].
P [ i ] [ j ] = true if substring str [ i . . j ] is palindrome , else false.
palindrome of single length.
palindrome of length 2.
Palindromes of length more than 2. This loop is similar to Matrix Chain Multiplication . We start with a gap of length 2 and fill DP table in a way that the gap between starting and ending indexes increase one by one by outer loop ..
Pick a starting point for the current gap.
Set ending point.
If current string is palindrome.
Add current palindrome substring ( + 1 ) and rest palindrome substring ( dp [ i ] [ j - 1 ] + dp [ i + 1 ] [ j ] ) remove common palindrome substrings ( - dp [ i + 1 ] [ j - 1 ] ).
return total palindromic substrings.
Driver Code"
Solution in Python:
assistant
#Here is code to count All Palindrome Sub and the other steps required.
 def CountPS ( str , n ) :
	dp = [ [ 0 for x in range ( n ) ] for y in range ( n ) ]
	P = [ [ False for x in range ( n ) ] for y in range ( n ) ]
	for i in range ( n ) :
		P [ i ] [ i ] = True
	for i in range ( n - 1 ) :
		if ( str [ i ] == str [ i + 1 ] ) :
			P [ i ] [ i + 1 ] = True
			dp [ i ] [ i + 1 ] = 1
	for gap in range ( 2 , n ) :
		for i in range ( n - gap ) :
			j = gap + i
			if ( str [ i ] == str [ j ] and P [ i + 1 ] [ j - 1 ] ) :
				P [ i ] [ j ] = True
			if ( P [ i ] [ j ] == True ) :
				dp [ i ] [ j ] = ( dp [ i ] [ j - 1 ] + dp [ i + 1 ] [ j ] + 1 - dp [ i + 1 ] [ j - 1 ] )
			else :
				dp [ i ] [ j ] = ( dp [ i ] [ j - 1 ] + dp [ i + 1 ] [ j ] - dp [ i + 1 ] [ j - 1 ] )
	return dp [ 0 ] [ n - 1 ]
if __name__ == " _ _ main _ _ " :
	str = " abaab "
	n = len ( str )
	print ( CountPS ( str , n ) )