Count All Palindrome Sub | Returns total number of palindrome substring of length greater then equal to 2 ; create 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 then 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 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 ; 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
< ? php function CountPS ( $ str , $ n ) { $ dp = array ( array ( ) ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) for ( $ j = 0 ; $ j < $ n ; $ j ++ ) $ dp [ $ i ] [ $ j ] = 0 ; $ P = array ( array ( ) ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) for ( $ j = 0 ; $ j < $ n ; $ j ++ ) $ P [ $ i ] [ $ j ] = false ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ P [ $ i ] [ $ i ] = true ; for ( $ i = 0 ; $ i < $ n - 1 ; $ i ++ ) { if ( $ str [ $ i ] == $ str [ $ i + 1 ] ) { $ P [ $ i ] [ $ i + 1 ] = true ; $ dp [ $ i ] [ $ i + 1 ] = 1 ; } } for ( $ gap = 2 ; $ gap < $ n ; $ gap ++ ) { for ( $ i = 0 ; $ i < $ n - $ gap ; $ i ++ ) { $ j = $ gap + $ i ; if ( $ str [ $ i ] == $ str [ $ j ] && $ 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 ] ; } $ str = " abaab " ; $ n = strlen ( $ str ) ; echo CountPS ( $ str , $ n ) ; ? >