Count palindromic characteristics of a String | PHP 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 function . ; 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
< ? php $ MAX_STR_LEN = 1000 ; $ P = array ( array ( ) ) ; $ Kpal = array_fill ( 0 , $ MAX_STR_LEN , 0 ) ; for ( $ i = 0 ; $ i < $ MAX_STR_LEN ; $ i ++ ) { for ( $ j = 0 ; $ j < $ MAX_STR_LEN ; $ j ++ ) $ P [ $ i ] [ $ j ] = false ; } function checkSubStrPal ( $ str , $ n ) { global $ P , $ Kpal , $ MAX_STR_LEN ; for ( $ i = 0 ; $ i < $ MAX_STR_LEN ; $ i ++ ) { for ( $ j = 0 ; $ j < $ MAX_STR_LEN ; $ j ++ ) $ P [ $ i ] [ $ j ] = false ; $ Kpal [ $ i ] = 0 ; } 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 ; 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 ; } } } function countKPalindromes ( $ i , $ j , $ k ) { global $ Kpal , $ P ; if ( $ i == $ j ) { $ Kpal [ $ k ] ++ ; return ; } if ( $ P [ $ i ] [ $ j ] == false ) return ; $ Kpal [ $ k ] ++ ; $ mid = ( $ i + $ j ) / 2 ; if ( ( $ j - $ i + 1 ) % 2 == 1 ) $ mid -- ; countKPalindromes ( $ i , $ mid , $ k + 1 ) ; } function printKPalindromes ( $ s ) { global $ P , $ Kpal , $ MAX_STR_LEN ; $ n = strlen ( $ s ) ; checkSubStrPal ( $ s , $ n ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) for ( $ j = 0 ; $ j < $ n - $ i ; $ j ++ ) countKPalindromes ( $ j , $ j + $ i , 1 ) ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) echo ( $ Kpal [ $ i ] . " ▁ " ) ; echo ( " STRNEWLINE " ) ; } $ s = " abacaba " ; printKPalindromes ( $ s ) ; ? >