小编Yia*_*nis的帖子

问题:需要两个字符串之间的LCS长度.字符串的大小最多为100个字符.字母表是通常的DNA,4个字符"ACGT".动态方法不够快.

我的问题是我正在处理很多对(我看到的数百万的等级).我相信我已经将LCS_length函数的调用减少到最小可能,因此使程序运行得更快的唯一方法是使用更高效的LCS_Length函数.

我已经开始实施通常的动态编程方法.这给出了正确答案,希望能够正确实施.

#define arrayLengthMacro(a) strlen(a) + 1
#define MAX_STRING 101

static int MaxLength(int lengthA, int lengthB);

/* 
 * Then the two strings are compared following a dynamic computing
 * LCS table algorithm. Since we only require the length of the LCS 
 * we can get this rather easily.
 */
int LCS_Length(char *a, char *b)
{
    int lengthA = arrayLengthMacro(a),lengthB = arrayLengthMacro(b), 
        LCS = 0, i, j, maxLength, board[MAX_STRING][MAX_STRING];

        maxLength = MaxLength(lengthA, lengthB);

    //printf("%d %d\n", lengthA, lengthB);
    for (i = …