資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會科學
時尚研究
法律研究最長公共子序列 C++ 語言程式
子序列是指順序相同的元素集合的序列。對於序列“stuv”，子序列為“stu”、“tuv”、“suv”，等等。
對於長度為 n 的字串，可以用 2n 種方式從字串中建立子序列。
示例
字串“ ABCDGH ”和“ AEDFHR ”的最長公共子序列的長度為 3。
#include <iostream>
#include <string.h>
using namespace std;
int max(int a, int b);
int lcs(char* X, char* Y, int m, int n){
if (m == 0 || n == 0)
return 0;
if (X[m - 1] == Y[n - 1])
return 1 + lcs(X, Y, m - 1, n - 1);
else
return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
}
int max(int a, int b){
return (a > b) ? a : b;
}
int main(){
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
int m = strlen(X);
int n = strlen(Y);
printf("Length of LCS is %d\n", lcs(X, Y, m, n));
return 0;
}輸出
Length of LCS is 4
更新於： 19-9-2019
2K+ 瀏覽次數
廣告