首页 > 代码库 > POJ 1458 最长公共子序列
POJ 1458 最长公共子序列
子序列就是子序列中的元素是母序列的子集,且子序列中元素的相对顺序和母序列相同。
题目要求便是寻找两个字符串的最长公共子序列。
dp[i][j]表示字符串s1左i个字符和s2左j个字符的公共子序列的最大长度。
注意s1第i个字符为s1[i-1]
于是有递推公式:
对于abcfbc和abfcab两个字符串,求公共子串的最大长度的过程如图:
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 1010; 8 char s1[maxn], s2[maxn]; 9 int dp[maxn][maxn];10 11 int main(void)12 {13 #ifdef LOCAL14 freopen("1458in.txt", "r", stdin);15 #endif16 17 while(cin >> s1 >> s2)18 {19 int Lenth1 = strlen(s1);20 int Lenth2 = strlen(s2);21 memset(dp, 0, sizeof(dp));22 23 int i, j;24 for(i = 1; i <= Lenth1; ++i)25 for(j = 1; j <= Lenth2; ++j)26 {27 if(s1[i-1] == s2[j-1])28 dp[i][j] = dp[i-1][j-1] + 1;29 else30 dp[i][j] = max(dp[i-1][j], dp[i][j-1]);31 }32 33 printf("%d\n", dp[Lenth1][Lenth2]);34 }35 return 0;36 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。