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.
User contributions licensed under CC BY-SA 3.0