LCS formed by consecutive segments of at least length K | CPP program to find the Length of Longest subsequence formed by consecutive segments of at least length K ; Returns the length of the longest common subsequence with a minimum of length of K consecutive segments ; length of strings ; declare the lcs and cnt array ; iterate from i = 1 to n and j = 1 to j = m ; stores the maximum of lcs [ i - 1 ] [ j ] and lcs [ i ] [ j - 1 ] ; when both the characters are equal of s1 and s2 ; when length of common segment is more than k , then update lcs answer by adding that segment to the answer ; formulate for all length of segments to get the longest subsequence with consecutive Common Segment of length of min k length ; update lcs value by adding segment length ; driver code to check the above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; int longestSubsequenceCommonSegment ( int k , string s1 , string s2 ) { int n = s1 . length ( ) ; int m = s2 . length ( ) ; int lcs [ n + 1 ] [ m + 1 ] ; int cnt [ n + 1 ] [ m + 1 ] ; memset ( lcs , 0 , sizeof ( lcs ) ) ; memset ( cnt , 0 , sizeof ( cnt ) ) ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= m ; j ++ ) { lcs [ i ] [ j ] = max ( lcs [ i - 1 ] [ j ] , lcs [ i ] [ j - 1 ] ) ; if ( s1 [ i - 1 ] == s2 [ j - 1 ] ) cnt [ i ] [ j ] = cnt [ i - 1 ] [ j - 1 ] + 1 ; if ( cnt [ i ] [ j ] >= k ) { for ( int a = k ; a <= cnt [ i ] [ j ] ; a ++ ) lcs [ i ] [ j ] = max ( lcs [ i ] [ j ] , lcs [ i - a ] [ j - a ] + a ) ; } } } return lcs [ n ] [ m ] ; } int main ( ) { int k = 4 ; string s1 = " aggasdfa " ; string s2 = " aggajasdfa " ; cout << longestSubsequenceCommonSegment ( k , s1 , s2 ) ; return 0 ; }