Find number of times a string occurs as a subsequence in given string | Iterative DP function to find the number of times the second string occurs in the first string , whether continuous or discontinuous ; Create a table to store results of sub - problems ; If second string is empty ; Fill lookup [ ] [ ] in bottom up manner ; If last characters are same , we have two options - 1. consider last characters of both strings in solution 2. ignore last character of first string ; If last character are different , ignore last character of first string ; Driver code
< ? php function count1 ( $ a , $ b ) { $ m = strlen ( $ a ) ; $ n = strlen ( $ b ) ; $ lookup = array_fill ( 0 , $ m + 1 , array_fill ( 0 , $ n + 1 , 0 ) ) ; for ( $ i = 0 ; $ i <= $ m ; ++ $ i ) $ lookup [ $ i ] [ 0 ] = 1 ; for ( $ i = 1 ; $ i <= $ m ; $ i ++ ) { for ( $ j = 1 ; $ j <= $ n ; $ j ++ ) { if ( $ a [ $ i - 1 ] == $ b [ $ j - 1 ] ) $ lookup [ $ i ] [ $ j ] = $ lookup [ $ i - 1 ] [ $ j - 1 ] + $ lookup [ $ i - 1 ] [ $ j ] ; else $ lookup [ $ i ] [ $ j ] = $ lookup [ $ i - 1 ] [ $ j ] ; } } return $ lookup [ $ m ] [ $ n ] ; } $ a = " GeeksforGeeks " ; $ b = " Gks " ; echo count1 ( $ a , $ b ) ; ? >