Find length of longest subsequence of one string which is substring of another string | Java program to find maximum length of subsequence of a string X such it is substring in another string Y . ; 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 Method
public class GFG { static final int MAX = 1000 ; static int maxSubsequenceSubstring ( char x [ ] , char y [ ] , int n , int m ) { int dp [ ] [ ] = new int [ MAX ] [ MAX ] ; for ( int i = 0 ; i <= m ; i ++ ) for ( int j = 0 ; j <= n ; j ++ ) dp [ i ] [ j ] = 0 ; for ( int i = 1 ; i <= m ; i ++ ) { for ( int 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 ] ; } } int ans = 0 ; for ( int i = 1 ; i <= m ; i ++ ) ans = Math . max ( ans , dp [ i ] [ n ] ) ; return ans ; } public static void main ( String [ ] args ) { char x [ ] = " ABCD " . toCharArray ( ) ; char y [ ] = " BACDBDCD " . toCharArray ( ) ; int n = x . length , m = y . length ; System . out . println ( maxSubsequenceSubstring ( x , y , n , m ) ) ; } }