C中3+序列的最长公共子序列
我已经写过LCS的部分了。
我想知道如果我给N(N>3)，这意味着有多少组输入。
就像这样：
输入
4 ab abc abcd abc ab
输出
3.
只需找到最长的那些lcs(3序列的一部分)
ab abc abcd->ab->2
abc abc->abc>3
3>2
我的想法是，每一个集合都使用3个序列的方式，然后找到最大的一个。
但我不知道怎么做或者其他更好的方法？
这是我代码的一部分：
#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;
}LCS：
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];
}谢谢大家~我用2d数组来存储序列来解决这个问题。
回答 1
Stack Overflow用户
发布于 2014-12-24 18:02:09
迭代过程可能是解决问题的一种方法。但是，最大长度的子序列可以在第一个字符串中到处开始。由于在过程中引入了一个新的字符串，仅保留当前的最大子序列是不够的。下面是一种存储字符串数组的方法：
char s[nb][N]; //nb strings of max length N-1您可以尝试保持数组int seqlen[j]的跟踪，直到第一个字符串s[0]，将最大公共子序列的长度存储在第一个字符串s[0]中的j位置。
初始化:如果s[0]是唯一的字符串，那么从j位置开始的最大公共子序列的长度是strlen(s[0])-j。
引入一个新的字符串s[i]：seqlen[j]需要更新(对于所有j)。创建s[0]当前子字符串的副本s[0]，从长度seqlen[j]的s[0][j]开始。这就是可以使用strstr(temp,s[i])的地方。当strstr()返回NULL和seqlen[j]>0时，通过在temp末尾引入空终止字符'\0'和减少seqlen[j]来缩小temp的大小。最后，seqlen[j]是从第一个字符串s[0]中的j位置开始的最大公共子序列的长度。
最后一步是取seqlen[j]的最大值，即最大公共子字符串的长度。此子字符串从j在s[0]中的相应位置开始。
内存占用和算法细化:找到最小的字符串并使用它作为s[0]。
算法精化:更新seqlen[j]的过程可以使用二进制搜索方法更新。
内存精化:使用malloc()为字符串数组分配内存，同时考虑字符串的确切长度。
https://stackoverflow.com/questions/27634165
复制相似问题
腾讯云开发者
