C语言编写， 练习七 LCS算法 目标：动态规划算法中的最长公共子串（LCS）算法，即找出两个序列中最长的公共子序列。 功能： 1.lcs2: 计算两个序列的LCS 2.修改help的提示以反映最新添加的命令 示例： (当两个序列为“ABCBDAB”，“BDCABA”) 1.>>>lcs2 Seq1: ABCBDAB (7) Seq2: BDCABA (6) LCS: BCBA (4) SimS: 0.62 (4/sqrt(7*6)) 其中：Seq1为序列1的内容和长度，LCS为最长公共子串及其长度, SimS为相似度。 (当两个序列为“ACCGGTCGAGTGCGCGGAAGCCGGCCGGAA”，“GTCGTTCGGAATGCCGTTGC TCTGTAAA”) 2.>>>lcs2 Seq1: ACCGGTCGAGTGCGCGGAAGCCGGCCGGAA (30) Seq2: GTCGTTCGGAATGCCGTTGCTCTGTAAA (28) LCS: GTCGTCGGAAGCCGGCCGAA (20) SimS: 0.69 (20/sqrt(30*28)) 提示： 1.在第一次实现LCS算法时，首先将两个序列固定，将LCS算法中的存储长度的dist数组和存储回溯路径的path数组设成固定维度的二维数组，便于调试代码； 2.两个序列相似度的计算公式为 strlen(lcs)/sqrt(strlen(seq1)*strlen(seq2))

以下是C语言实现的LCS算法示例代码，供参考：

#include <stdio.h>
#include <string.h>
#include <math.h>

#define MAXLEN 1000

int dist[MAXLEN][MAXLEN];
int path[MAXLEN][MAXLEN];

void lcs2(char* seq1, char* seq2) {
    int len1 = strlen(seq1);
    int len2 = strlen(seq2);

    // 初始化dist和path数组
    for (int i = 0; i <= len1; i++) {
        dist[i][0] = 0;
        path[i][0] = 0;
    }
    for (int j = 0; j <= len2; j++) {
        dist[0][j] = 0;
        path[0][j] = 0;
    }

    // 动态规划计算dist和path数组
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (seq1[i-1] == seq2[j-1]) {
                dist[i][j] = dist[i-1][j-1] + 1;
                path[i][j] = 1;
            } else if (dist[i-1][j] >= dist[i][j-1]) {
                dist[i][j] = dist[i-1][j];
                path[i][j] = 2;
            } else {
                dist[i][j] = dist[i][j-1];
                path[i][j] = 3;
            }
        }
    }

    // 从path数组中回溯出LCS
    int i = len1, j = len2, k = dist[len1][len2];
    char lcs[MAXLEN];
    while (k > 0) {
        if (path[i][j] == 1) {
            lcs[--k] = seq1[i-1];
            i--; j--;
        } else if (path[i][j] == 2) {
            i--;
        } else {
            j--;
        }
    }

    // 输出结果
    printf("Seq1: %s (%d)\n", seq1, len1);
    printf("Seq2: %s (%d)\n", seq2, len2);
    printf("LCS: ");
    for (int i = 0; i < dist[len1][len2]; i++) {
        printf("%c", lcs[i]);
    }
    printf(" (%d)\n", dist[len1][len2]);
    printf("SimS: %.2f\n", dist[len1][len2]/sqrt(len1*len2));
}

int main() {
    char seq1[] = "ABCBDAB";
    char seq2[] = "BDCABA";
    lcs2(seq1, seq2);

    char seq3[] = "ACCGGTCGAGTGCGCGGAAGCCGGCCGGAA";
    char seq4[] = "GTCGTTCGGAATGCCGTTGCTCTGTAAA";
    lcs2(seq3, seq4);

    return 0;
}

输出结果为：

Seq1: ABCBDAB (7)
Seq2: BDCABA (6)
LCS: BCBA (4)
SimS: 0.62
Seq1: ACCGGTCGAGTGCGCGGAAGCCGGCCGGAA (30)
Seq2: GTCGTTCGGAATGCCGTTGCTCTGTAAA (28)
LCS: GTCGTCGGAAGCCGGCCGAA (20)
SimS: 0.69

其中，dist数组存储了最长公共子序列的长度，path数组存储了回溯路径，用于回溯出最长公共子序列。最后根据公式计算出相似度SimS。