首页 > 代码库 > 编程算法 - 最长公共子序列(LCS) 代码(C)
编程算法 - 最长公共子序列(LCS) 代码(C)
最长公共子序列(LCS) 代码(C)
本文地址: http://blog.csdn.net/caroline_wendy
题目: 给定两个字符串s,t, 求出这两个字符串最长的公共子序列的长度. 字符串的子序列并一定要连续, 能够包含间隔.
即最长公共子序列问题(LCS, Longest Common Subsequence)
使用动态规划, 假设字符相等, 两个字符串就依次递增一位, 一直到字符串的结尾.
代码:
/* * main.cpp * * Created on: 2014.7.17 * Author: spike */ /*eclipse cdt, gcc 4.8.1*/ #include <stdio.h> #include <memory.h> #include <limits.h> #include <utility> #include <queue> #include <algorithm> using namespace std; class Program { static const int MAX_N = 100; int n=4, m=4; char s[MAX_N] = "abcd", t[MAX_N] = "becd"; int dp[MAX_N+1][MAX_N+1]; public: void solve() { for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { if (s[i]==t[j]) { dp[i+1][j+1] = dp[i][j]+1; } else { dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]); } } } printf("result = %d\n", dp[n][m]); } }; int main(void) { Program P; P.solve(); return 0; }
输出:
result = 3
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。