Number of palindromic subsequences of length k where k <= 3 | PHP program to count number of subsequences of given length . ; Precompute the prefix and suffix array . ; Precompute the prefix 2D array ; Precompute the Suffix 2D array . ; Find the number of palindromic subsequence of length k ; If k is 1. ; If k is 2 ; Adding all the products of prefix array ; For k greater than 2. Adding all the products of value of prefix and suffix array . ; Driver Code
< ? php $ MAX = 100 ; $ MAX_CHAR = 26 ; function precompute ( $ s , $ n , & $ l , & $ r ) { global $ MAX , $ MAX_CHAR ; $ l [ ord ( $ s [ 0 ] ) - ord ( ' a ' ) ] [ 0 ] = 1 ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { for ( $ j = 0 ; $ j < $ MAX_CHAR ; $ j ++ ) $ l [ $ j ] [ $ i ] += $ l [ $ j ] [ $ i - 1 ] ; $ l [ ord ( $ s [ $ i ] ) - ord ( ' a ' ) ] [ $ i ] ++ ; } $ r [ ord ( $ s [ $ n - 1 ] ) - ord ( ' a ' ) ] [ $ n - 1 ] = 1 ; for ( $ i = $ n - 2 ; $ i >= 0 ; $ i -- ) { for ( $ j = 0 ; $ j < $ MAX_CHAR ; $ j ++ ) $ r [ $ j ] [ $ i ] += $ r [ $ j ] [ $ i + 1 ] ; $ r [ ord ( $ s [ $ i ] ) - ord ( ' a ' ) ] [ $ i ] ++ ; } } function countPalindromes ( $ k , $ n , & $ l , & $ r ) { global $ MAX , $ MAX_CHAR ; $ ans = 0 ; if ( $ k == 1 ) { for ( $ i = 0 ; $ i < $ MAX_CHAR ; $ i ++ ) $ ans += $ l [ $ i ] [ $ n - 1 ] ; return $ ans ; } if ( $ k == 2 ) { for ( $ i = 0 ; $ i < $ MAX_CHAR ; $ i ++ ) $ ans += ( ( $ l [ $ i ] [ $ n - 1 ] * ( $ l [ $ i ] [ $ n - 1 ] - 1 ) ) / 2 ) ; return $ ans ; } for ( $ i = 1 ; $ i < $ n - 1 ; $ i ++ ) for ( $ j = 0 ; $ j < $ MAX_CHAR ; $ j ++ ) $ ans += $ l [ $ j ] [ $ i - 1 ] * $ r [ $ j ] [ $ i + 1 ] ; return $ ans ; } $ s = " aabab " ; $ k = 2 ; $ n = strlen ( $ s ) ; $ l = array_fill ( 0 , $ MAX_CHAR , array_fill ( 0 , $ MAX , NULL ) ) ; $ r = array_fill ( 0 , $ MAX_CHAR , array_fill ( 0 , $ MAX , NULL ) ) ; precompute ( $ s , $ n , $ l , $ r ) ; echo countPalindromes ( $ k , $ n , $ l , $ r ) . " " ; ? >