Count All Palindromic Subsequence in a given String | Function return the total palindromic subsequence ; create a 2D array to store the count of palindromic subsequence ; palindromic subsequence of length 1 ; check subsequence of length L is palindrome or not ; return total palindromic subsequence ; Driver Code
< ? php function countPS ( $ str ) { $ N = strlen ( $ str ) ; $ cps = array_fill ( 0 , $ N + 1 , array_fill ( 0 , $ N + 1 , NULL ) ) ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) $ cps [ $ i ] [ $ i ] = 1 ; for ( $ L = 2 ; $ L <= $ N ; $ L ++ ) { for ( $ i = 0 ; $ i <= $ N - $ L ; $ i ++ ) { $ k = $ L + $ i - 1 ; if ( $ str [ $ i ] == $ str [ $ k ] ) $ cps [ $ i ] [ $ k ] = $ cps [ $ i ] [ $ k - 1 ] + $ cps [ $ i + 1 ] [ $ k ] + 1 ; else $ cps [ $ i ] [ $ k ] = $ cps [ $ i ] [ $ k - 1 ] + $ cps [ $ i + 1 ] [ $ k ] - $ cps [ $ i + 1 ] [ $ k - 1 ] ; } } return $ cps [ 0 ] [ $ N - 1 ] ; } $ str = " abcb " ; echo " Total ▁ palindromic ▁ subsequence ▁ are ▁ : ▁ " . countPS ( $ str ) . " STRNEWLINE " ; ? >