I'm having difficulty understanding the code for the Longest Common Substring problem on my regular resource. I'm not getting the desired output when I try to run the code. Here is the code I'm trying to use:

// Function to find Longest Common Substring

// of two given strings

string LCS(string X, string Y)

{

// Find lengths of given strings

intm = X.length ();

int n = Y.length();




// Declare the 2D array

int L[m+1][n+1];




//Fill values ​​​​in the array

for (int i = 0; i <= m; i++)

{

for (int j = 0; j <= n; j++)

{

if (i == 0 || j == 0)

Lj = 0;

else if (X[i - 1] == Y[j - 1])

L j = L[i - 1][j - 1] + 1;

else

L j = max(L[i - 1]j, L [j - 1]);

}

}




// Backtrack to find the substring

int index = Lmn;




// Create a string length index+1

string lcs(index+1, ' ');




// Start from the right-most-bottom-most corner

// and one by one store characters in lcs[]

int i = m, j = n;

while (i > 0 && j > 0)

{

// If current character in X[] and Y are same

if (X[i - 1] == Y[j - 1])

{

// Put current character into result

lcs [index - 1] = X[i - 1];




// reduce values ​​of i, j and index

the--;

j--;

index--;

}




// If not same, then find the larger of two and

// go in the direction of larger values

​​else if (L[i - 1]j > L [j - 1])

the--;

else

j--;

}




// Return the result

return lcs;

}

I'm hoping someone can help me figure out what's wrong with the code and help me get the desired output. Thanks in advance!


--- Ultima modifica di Rosaline in data 2023-04-19 14:08:33 ---

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>




using namespace std;




// Function to find the Longest Common Substring

string LCS(string X, string Y) {

// Find lengths of given strings

int m = X.length();

int n = Y.length();




// Declare the 2D array to store lengths of longest common suffixes

vector<vector<int>> L(m + 1, vector<int>(n + 1, 0));




// Variable to keep track of the maximum length of LCS

int maxLength = 0;

int endIdx = 0; // To store the end index of the longest common substring in X




// Fill the array with values

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= n; j++) {

if (X[i - 1] == Y[j - 1]) {

Lj = L[i - 1][j - 1] + 1;




// Update maxLength if a longer common substring is found

if (Lj > maxLength) {

maxLength = Lj;

endIdx = i - 1;

}

} else {

Lj = 0;

}

}

}




// If there is no common substring, return an empty string

if (maxLength == 0) {

return "";

}




// Extract the longest common substring

return X.substr(endIdx - maxLength + 1, maxLength);

}




int main() {

string X = "ABABC";

string Y = "BABC";




cout << "Longest Common Substring: " << LCS(X, Y) << endl;




return 0;

}

Initialization ofL : Used a vector of vectors to declare a 2D array with zero-initialized values ​​to store lengths of common substrings at each point.Array Access Errors : Fixed the syntax and index accesses, ensuring Ljit was updated correctly.Tracking Max Length and End Index : Added variables maxLengthand endIdxto keep track of the longest common substring's length and where it ends.Return Statement : Used substrto return the longest substring based on the endIdxand maxLength.

Please stay on topic.

This resource is dedicated to Python and related topics.

Thank you.

Hello, can I have the full code?