Trying to print the LCS of 3 and 4 strings but it wont work

-1

I'm working on a program that prints the largest common sub-sequence of 2,3 or 4 strings using dynamic programming.

I was successfully able to get the LCS of 2 strings without any issue at all using this.

I had also already run the Max function for lcsLen and it is populated with the correct values and is returning the correct length without any issue

   int index = lcsLen[size1][size2];

   lcs = new char[index+1];
   lcs[index] = '\0';

   int i = size1, j = size2;
   while (i > 0 && j > 0) {

       if (st1[i - 1] == st2[j - 1]) {
           lcs[index - 1] = st1[i - 1];
           i--;
           j--;
           index--; 
       }


       else if (lcsLen[i - 1][j] > lcsLen[i][j - 1])
           i--;
       else
           j--;
   }

but when modifying the algorithm for 3 strings i run into an infinite loop or a weird exit code

   int index = lcsLen[size1][size2][size3];

   lcs = new char[index+1];
   lcs[index] = '\0';

   int i = size1, j = size2, k = size3;
   while (i > 0 && j > 0 && k > 0) {
       if (st1[i - 1] == st2[j - 1] && st1[i - 1] == st3[k - 1]) {
           lcs[index - 1] = st1[i - 1];
           i--;
           j--;
           k--;
           index--; 

       }

       else if (lcsLen[i - 1][j][k] > lcsLen[i][j - 1][k] && lcsLen[i - 1][j][k] > lcsLen[i][j][k - 1])
           i--;
       else if (lcsLen[i][j - 1][k] > lcsLen[i - 1][j][k] && lcsLen[i][j - 1][k] > lcsLen[i][j][k - 1])
           j--;
       else
           k--;
   }

I used a debugger and noticed that it specifically will not get past this specific line

if (st1[i - 1] == st2[j - 1] && st1[i - 1] == st3[k - 1])

st1,sr2,st3,st4 are all dynamic char arrays and even when they all have matching values they will not execute what is inside the if statement and run infinitely or my compiler will throw this exit code "-1073741819 (0xC0000005)". it does one or the other randomly and I'm very confused

Have i written the algorithm wrong? and if so whats the correct way of writing it for both 3 strings and 4 strings.

c++
asked on Stack Overflow Jan 30, 2019 by Imad • edited Jan 30, 2019 by Imad

0 Answers

Nobody has answered this question yet.


User contributions licensed under CC BY-SA 3.0