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