Find length of longest subsequence of one string which is substring of another string | Return the maximum size of substring of X which is substring in Y . ; Initialize the dp [ ] [ ] to 0. ; Calculating value for each element . ; If alphabet of string X and Y are equal make dp [ i ] [ j ] = 1 + dp [ i - 1 ] [ j - 1 ] ; Else copy the previous value in the row i . e dp [ i - 1 ] [ j - 1 ] ; Finding the maximum length . ; Driver Code
< ? php function maxSubsequenceSubstring ( $ x , $ y , $ n , $ m ) { $ dp ; for ( $ i = 0 ; $ i <= $ m ; $ i ++ ) for ( $ j = 0 ; $ j <= $ n ; $ j ++ ) $ dp [ $ i ] [ $ j ] = 0 ; for ( $ i = 1 ; $ i <= $ m ; $ i ++ ) { for ( $ j = 1 ; $ j <= $ n ; $ j ++ ) { if ( $ x [ $ j - 1 ] == $ y [ $ i - 1 ] ) $ dp [ $ i ] [ $ j ] = 1 + $ dp [ $ i - 1 ] [ $ j - 1 ] ; else $ dp [ $ i ] [ $ j ] = $ dp [ $ i ] [ $ j - 1 ] ; } } $ ans = 0 ; for ( $ i = 1 ; $ i <= $ m ; $ i ++ ) $ ans = max ( $ ans , $ dp [ $ i ] [ $ n ] ) ; return $ ans ; } { $ x = " ABCD " ; $ y = " BACDBDCD " ; $ n = strlen ( $ x ) ; $ m = strlen ( $ y ) ; echo maxSubsequenceSubstring ( $ x , $ y , $ n , $ m ) ; return 0 ; } ? >