Longest Matched Substring confusion / clarification

[meegsees]

This is more of a "can you help clarify?" ~ the below is the full assignment I was handed, with no additional explanation.

-----------
Consider two strings as follows.
ABCBDAB
BDCABA

The “longest matched substring allowing for gaps” (LMSAFG) is the longest (could be a tie) such substring matched between the two strings such that gaps are allowed but the sequence is maintained (in either direction). So, the LMSAFG are as follows in the given example:
BCBA, BCAB, BDAB, BADB, BACB, ABCB

Write a program in C++ to print all such LMSAFG using the above test.
----------

I've done my research online, read through the geekforgeeks pages, the wikibooks for "longest common substring"

As well, we've already done an assignment for all unique substrings of a full string, so I know that's not what is to be accomplished with this assignment. What I'm assuming is a variation of the code below to print out ALL of the variations, not just one? And if so, after a few hours of trial an error, at least with this code, I'm not sure how to implement it exactly so that it would print out a list as shown in the assignment, as well as any additional not included.

  #include <iostream>
#include <algorithm>

using namespace std;
 
//Prints the Longest common subsequence
void printLCS( char *s1, char *s2, int m, int n )
{
   int L[m+1][n+1];
 
   //Building L[m][n] as in algorithm
   for (int i=0; i<=m; i++)
   {
     for (int j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;
       else if (s1[i-1] == s2[j-1])
         L[i][j] = L[i-1][j-1] + 1;
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }
 
   //To print LCS
   int index = L[m][n];
   //charcater array to store LCS
   char LCS[index+1];
   LCS[index] = '\0'; // Set the terminating character
   
   //Stroing characters in LCS
   //Start from the right bottom corner character
   int i = m, j = n;
   while (i > 0 && j > 0)
   {
      //if current character in s1 and s2 are same, then include this character in LCS[]
      if (s1[i-1] == s2[j-1])
      {
          LCS[index-1] = s1[i-1]; // Put current character in result
          i--; j--; index--;     // reduce values of i, j and index

      }
      // compare values of L[i-1][j] and L[i][j-1] and go in direction of greater value.
      else if (L[i-1][j] > L[i][j-1])
         i--;
      else
         j--;
   }
 
   // Print the LCS
   cout << "LCS of " << s1 << " and " << s2 << " is "<< endl << LCS << endl;
}
 
/* Driver program to test above function */
int main()
{
  char s1[] = "ABCBDAB";
  char s2[] = "BDCABA";
  printLCS(s1, s2, strlen(s1), strlen(s2));
  return 0;
}

[meegsees]

So the general consensus from a few classmates is the print out is supposed to be all of the substrings. *cry*

"Be a programmer!" they said... "It'll be fun!" they said...

[lastchance]

@meegsees,
You can do it recursively.

Consider just the forward direction for both strings first. (You can put these results in a set, and then repeat with both strings reversed afterwards.

For example, with the example you gave, you would have (scanning the shorter string for start points, and noting that the other substring must start after the first occurrence):

LCS( BDCABA,ABCBDAB) = vector of the max length sequences from:
  B + LCS(DCABA,CBDAB)
  D + LCS(CABA,AB)
  C + LCS(ABA,BDAB)
  A + LCS(BA,BCBDAB)
  B + LCS(A,CBDAB)
  A

Each function call should return a vector of the longest acceptable sequences.

If you evaluate the maximum by taking these from the first letter forwards, then you don't actually have to evaluate all of these: here, you wouldn't need to consider the last three since they couldn't possibly produce the longest sequence once you had some of length 4, whilst it isn't necessary to consider any particular letter that has previously been used as starter since any sequences would already have been covered by that starter.



Output:

Each string taken forward only:
BCAB BCBA BDAB 
Both strings taken forwards or both taken backwards:
ABCB BACB BADB BCAB BCBA BDAB