Find the longest subsequence of a string that is a substring of another string | C ++ program for the above approach ; Function to find the longest subsequence that matches with the substring of other string ; Stores the lengths of strings X and Y ; Create a matrix ; Initialize the matrix ; Fill all the remaining rows ; If the characters are equal ; If not equal , then just move to next in subsequence string ; Find maximum length of the longest subsequence matching substring of other string ; Iterate through the last row of matrix ; Store the required string ; Backtrack from the cell ; If equal , then add the character to res string ; Return the required string ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; string longestSubsequence ( string X , string Y ) { int n = X . size ( ) ; int m = Y . size ( ) ; vector < vector < int > > mat ( n + 1 , vector < int > ( m + 1 ) ) ; for ( int i = 0 ; i < n + 1 ; i ++ ) { for ( int j = 0 ; j < m + 1 ; j ++ ) { if ( i == 0 j == 0 ) mat [ i ] [ j ] = 0 ; } } for ( int i = 1 ; i < n + 1 ; i ++ ) { for ( int j = 1 ; j < m + 1 ; j ++ ) { if ( X [ i - 1 ] == Y [ j - 1 ] ) { mat [ i ] [ j ] = 1 + mat [ i - 1 ] [ j - 1 ] ; } else { mat [ i ] [ j ] = mat [ i - 1 ] [ j ] ; } } } int len = 0 , col = 0 ; for ( int i = 0 ; i < m + 1 ; i ++ ) { if ( mat [ n ] [ i ] > len ) { len = mat [ n ] [ i ] ; col = i ; } } string res = " " ; int i = n ; int j = col ; while ( len > 0 ) { if ( X [ i - 1 ] == Y [ j - 1 ] ) { res = X [ i - 1 ] + res ; i -- ; j -- ; len -- ; } else { i -- ; } } return res ; } int main ( ) { string X = " ABCD " ; string Y = " ACDBDCD " ; cout << ( longestSubsequence ( X , Y ) ) ; return 0 ; }