Given two strings s1, s2 and K, find the length of the longest subsequence formed by consecutive segments of at least length K.

Examples:

Input : s1 =aggayxysdfas2 =aggajxaaasdfak = 4 Output : 8 Explanation:aggasdfais the longest subsequence that can be formed by taking consecutive segments, minimum of length 4. Here segments are "agga" and "sdfa" which are of length 4 which is included in making the longest subsequence. Input : s1 = aggasdfas2 = aggajasdfaxy k = 5 Output : 5 Input: s1 = "aabcaaaa" s2 = "baaabcd" k = 3 Output: 4 Explanation: "aabc" is the longest subsequence that is formed by taking segment of minimum length 3. The segment is of length 4.

**Prerequisite **: Longest Common Subsequence

Create a LCS[][] array where LCS_{i, j} denotes the length of the longest common subsequence formed by characters of s1 till i and s2 till j having consecutive segments of at least length K. Create a cnt[][] array to count the length of the common segment. **cnt _{i, j}= cnt_{i-1, j-1}+1** when s1[i-1]==s2[j-1]. If characters are not equal then segments are not equal hence mark cnt

_{i, j}as 0.

When

**cnt**, then update the lcs value by adding the value of cnt

_{i, j}>=k_{i-a, j-a}where a is the length of the segments

**a<=cnt**. The answer for the longest subsequence with consecutive segments of at least length k will be stored in

_{i, j}**lcs[n][m]**where n and m are the length of string1 and string2.

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

**Output:**

8

If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

more link ADS

Smart Retail, Smart Agriculture, Smart supply Chain, Smart Health, Smart energy, Smart City

Blockchain, bitcoin, ethereum, blockchain technology, cryptocurrencies

Information Security, latest Hacking News, Cyber Security, Network Sec

Information Security, latest Hacking News, Cyber Security, Network Security

Blog! Development Software and Application Mobile

Development apps, Android, Ios anh Tranning IT, data center, hacking

Car News, Reviews, Pricing for New & Used Cars, car reviews and news, concept cars

Travel Blog is a unique free online travel diary for travellers across the world.