首页 > 其他 > 详细

编程算法 - 最长公共子序列(LCS) 代码(C)

时间:2014-07-19 09:06:57      阅读:355      评论:0      收藏:0      [点我收藏+]

最长公共子序列(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




bubuko.com,布布扣




编程算法 - 最长公共子序列(LCS) 代码(C),布布扣,bubuko.com

编程算法 - 最长公共子序列(LCS) 代码(C)

原文:http://www.cnblogs.com/mengfanrong/p/3854394.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!