Longest common subsequence for 3+ sequences in c
I've already written the LCS part.
I want to know. If I give N (N> 3) it means how many sets of input.
Like
this:
Input :
4 ab abc abcd abcde
Output :
3
Just find the longest of these lcs (3 sequences part)
ab abc abcd-> ab-> 2
abc abcd abcde-> abc-> 3
3> 2
My thinking is that each set number simply uses a three-sequence path and then finds the largest. But I don't know how to do it or is it better?
This is part of my code:
#define EQUAL(x,y,z) ((x)==(y)&&(y)==(z))
int main(){
int set;
int longest;
while (scanf("%d", &set) != EOF){
while (set){
scanf("%s", c1);
set--;
scanf("%s", c2);
set--;
scanf("%s", c3);
set--;
longest = LCS(strlen(c1), strlen(c2), strlen(c3));
}
}
return 0;
}
HDL:
int LCS(int c1_length, int c2_length, int c3_length)
{
memset(lcs, 0, N*N);
int i;
int j;
int k;
for (i = 1; i <= c1_length; i++)
for (j = 1; j <= c2_length; j++)
for (k = 1; k <= c3_length; k++)
{
if (EQUAL(c1[i], c2[j], c3[k]))
lcs[i][j][k] = lcs[i - 1][j - 1][k - 1] + 1;
else
lcs[i][j][k] = max(lcs[i - 1][j][k], lcs[i][j - 1][k], lcs[i][j][k - 1]);
}
return lcs[i - 1][j - 1][k - 1];
}
Thanks everyone ~ I solved this question using a 2d array to keep the sequence.
source to share
An iterative procedure might be the way to solve your problem. But a subsequence of maximum length can start anywhere in the first line. Since a new procedure is introduced into the procedure, keeping the current maximum subsequence is not sufficient. Here's a way to store an array of strings:
char s[nb][N]; //nb strings of max length N-1
You can try to keep a trace of the array int seqlen[j]
if the first is line s[0]
, keeping the length of the maximum common subsequence starting from the location j
on the first line s[0]
.
Initialization: if s[0]
is a single string, then the length of the maximum common subsequence starting with a place j
isstrlen(s[0])-j
Introducing a new line s[i]
: seqlen[j]
needs to be updated (for all j). Create a copy of the temp
current substring s[0]
starting at s[0][j]
length seqlen[j]
. Here you can use strstr(temp,s[i])
. While it strstr()
returns NULL and seqlen[j]>0
, decrease the size temp
by entering a null character '\0'
at the end temp
and decrease seqlen[j]
. At the end, seqlen[j]
is the length of the maximum common subsequence, starting from the position j
on the first line s[0]
.
The last step is to take the maximum seqlen[j]
, that is, the length of the largest common substring. This substring starts at the corresponding position j
ins[0]
Memory footprint and algorithmic refinement: find the smallest string and use it like s[0]
.
Algorithmic refinement: The update procedure seqlen[j]
can be updated using the binary search method.
Memory Refinement: Allocate memory for an array of strings with malloc()
, while taking the exact length of the strings.
source to share