c - c中3个以上序列的最长公共(public)子序列

Question

我已经写了LCS的部分。
我想知道如果我给N(N>3)，那意味着有多少组输入。
像这样:
输入:
4 ab abc abcd abcde
输出:
3
找到最长的lcs(3个sequences a part)
ab abc abcd->ab->2
abc abcd abcde->abc->3
3> 2
我的想法是每个set的数量就是用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;
}

濒海战斗舰:

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];
    }

谢谢大家~我用二维数组存储序列解决了这道题

Answer 1

迭代过程可能是解决您的问题的一种方法。但是最大长度的子序列可以从第一个字符串的任何地方开始。由于在过程中引入了一个新的字符串，保持当前的最大子序列是不够的。这是一种存储字符串数组的方法:

char s[nb][N]; //nb strings of max length N-1

你可以尝试跟踪一个数组int seqlen[j]，只要第一个字符串s[0]，存储最大公共(public)长度从第一个字符串 s[0] 中的位置 j 开始的子序列。

初始化:如果s[0]是唯一的字符串，那么从j开始的最大公共(public)子序列的长度是strlen(s[0 ])-j

引入一个新的字符串s[i]:seqlen[j]需要更新(对于所有j)。创建 s[0] 的当前子字符串的副本 temp，从 s[0][j] 开始，长度为 seqlen [j]。这是可以使用 strstr(temp,s[i]) 的地方。当 strstr() 返回 NULL 和 seqlen[j]>0 时，通过引入空终止字符 ' 来减小 temp 的大小\0' 在 temp 的末尾并减少 seqlen[j]。最后，seqlen[j]是第一个字符串s[0]中从j处开始的最大公共(public)子序列的长度。

最后一步是取seqlen[j]的最大值，即最大公共(public)子串的长度。此子字符串从 s[0]

中对应的位置 j 开始

内存占用和算法改进:找到最小的字符串并将其用作 s[0]。

算法改进:更新 seqlen[j] 的过程可以使用二进制搜索方法进行更新。

内存优化:使用 malloc() 为字符串数组分配内存，同时考虑字符串的确切长度。