Count distinct occurrences as a subsequence | PHP program to count number of times S appears as a subsequence in T ; T can 't appear as a subsequence in S ; mat [ i ] [ j ] stores the count of occurrences of T ( 1. . i ) in S ( 1. . j ) . ; Initializing first column with all 0 s . An empty string can 't have another  string as suhsequence ; Initializing first row with all 1 s . An empty string is subsequence of all . ; Fill mat [ ] [ ] in bottom up manner ; If last characters don 't match,  then value is same as the value  without last character in S. ; Else value is obtained considering two cases . a ) All substrings without last character in S b ) All substrings without last characters in both . ; uncomment this to print matrix mat for ( int i = 1 ; i <= m ; i ++ , cout << endl ) for ( int j = 1 ; j <= n ; j ++ ) cout << mat [ i ] [ j ] << " ▁ " ; ; Driver Code
< ? php function findSubsequenceCount ( $ S , $ T ) { $ m = strlen ( $ T ) ; $ n = strlen ( $ S ) ; if ( $ m > $ n ) return 0 ; $ mat = array ( array ( ) ) ; for ( $ i = 1 ; $ i <= $ m ; $ i ++ ) $ mat [ $ i ] [ 0 ] = 0 ; for ( $ j = 0 ; $ j <= $ n ; $ j ++ ) $ mat [ 0 ] [ $ j ] = 1 ; for ( $ i = 1 ; $ i <= $ m ; $ i ++ ) { for ( $ j = 1 ; $ j <= $ n ; $ j ++ ) { if ( $ T [ $ i - 1 ] != $ S [ $ j - 1 ] ) $ mat [ $ i ] [ $ j ] = $ mat [ $ i ] [ $ j - 1 ] ; else $ mat [ $ i ] [ $ j ] = $ mat [ $ i ] [ $ j - 1 ] + $ mat [ $ i - 1 ] [ $ j - 1 ] ; } } return $ mat [ $ m ] [ $ n ] ; } $ T = " ge " ; $ S = " geeksforgeeks " ; echo findSubsequenceCount ( $ S , $ T ) . " " ;