前言

什么是最長公共子序列呢?好比一個數列 S，如果分別是兩個或多個已知數列的子序列，且是所有符合此條件序列中最長的，則S 稱為已知序列的最長公共子序列。

如何解決

通用的解法用動態規劃，如何使用動態規劃解題，晚上已經有很多不同人的答案了，推薦幾個：
程序員編程藝術第十一章：最長公共子序列(LCS)問題
算法導論—–最長公共子序列LCS（動態規劃）

我的代碼

c語言

#include<stdio.h>
#include<stdlib.h>
#include<string.h>#define N 10005int dp[N][N];
int b[N][N];void lcs(const char* s1, const char* s2)
{int len_s1 = strlen(s1);int len_s2 = strlen(s2);for (int i = 0; i <= len_s1; i++){dp[i][0] = 0;}for (int j = 0; j <= len_s2; j++){dp[0][j] = 0;}for (int i = 1; i <= len_s1; i++){for (int j = 1; j <= len_s2; j++){if (s1[i - 1] == s2[j - 1]){dp[i][j] += dp[i - 1][j - 1] + 1;b[i][j] = 1;}else if (dp[i - 1][j] >= dp[i][j - 1]){dp[i][j] = dp[i - 1][j];b[i][j] = 3; // 取上一層}else{dp[i][j] = dp[i][j - 1];b[i][j] = 2; //取左一列}}}
}void print_lcs(const char* x, int i, int j)
{if (i == 0 || j == 0){return ;}if (b[i][j] == 1){print_lcs(x, i - 1, j - 1);printf("%c", x[i - 1]);}else if (b[i][j] == 3){print_lcs(x, i - 1, j);}else{print_lcs(x, i, j - 1);}
}int main()
{//const char *s1 = "ABCBDAB";//const char *s2 = "BDCABA";char s1[100], s2[100];scanf("%s", s1);scanf("%s", s2);int len_s1 = strlen(s1);int len_s2 = strlen(s2);lcs(s1, s2);print_lcs(s1, len_s1, len_s2);printf("\n");return 0;
}

python

#!/bin/pythonimport sys,osres = []
def lcs(str1, str2):len_str1 = len(str1)len_str2 = len(str2)dp = [[0] * (len_str2+1) for _ in range(len_str1+1)]b = [[0] * (len_str2+1) for _ in range(len_str1+1)]for i in range(1, len_str1 + 1):for j in range(1, len_str2 + 1):if str1[i - 1] == str2[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1b[i][j] = 1elif dp[i-1][j] >= dp[i][j - 1]:dp[i][j] = dp[i - 1][j]b[i][j] = 3else:dp[i][j] = dp[i][j - 1]b[i][j] = 2return bdef print_lcs(str1, b, i, j):if i == 0 or j == 0:returnif b[i][j] == 1:print_lcs(str1, b, i - 1, j - 1)res.append(str1[i - 1])elif b[i][j] == 3:print_lcs(str1, b, i - 1, j)else:print_lcs(str1, b, i, j - 1)def main():str1 = sys.stdin.readline().strip()str2 = sys.stdin.readline().strip()#print(str1, str2)b = lcs(str1, str2)#print(b)print_lcs(str1, b, len(str1), len(str2))print(''.join(res))if __name__ == '__main__':main()

測試

ABCBDAB
BDCABAres:
BCBA

總結

以上是生活随笔為你收集整理的计算最长公共子序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。