[ACM_ZOJ_1733]Longest Common Subsequence

杰拉斯 | 时间：2012-04-04, Wed | 40,681 views
编程算法　

Common Subsequence
（最长公共子序列）

Time Limit: 2 Seconds Memory Limit: 65536 KB

Description

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = another sequence Z = is a subsequence of X if there exists a strictly increasing sequence of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = is a subsequence of X = with index sequence . Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.

The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.

Sample Input

abcfbc abfcab
programming contest
abcd mnp

Sample Output

4
2
0

Source

ZOJ1733（英文） NYOJ36（中文）

本题是动态规划的经典题目，求两个字符串的最长公共子序列，关于求单个字符串的最长有序子序列（较为简单），请看文章：[ACM_POJ_2533]Longest Ordered Subsequence。

思路分析：

设c[i][j]为字符串a的第i个字符与字符串b的第j个字符为止的最长公共子序列长度，那么有两种情况：

当a[i] == b[j]时，c[i][j]应该是前一个状态的最长公共子序列长度 + 1，而前一个状态是c[i - 1][j]呢，还是c[i][j - 1]？两者都不是，因为a[i]与b[j]匹配，a[i]与b[j]必然不能已经匹配过，否则就是同一个字母匹配了多次，这必然是非法的，因此上一个状态应是c[i - 1][j - 1]，即c[i][j] = c[i - 1][j - 1] + 1；
当a[i] != b[j]时，上一个状态可能是c[i - 1][j]或c[i][j - 1]，而既然要找最长公共子序列，自然是找最大的一个，即c[i][j] = max(c[i - 1][j], c[i][j - 1])。

辅助空间变化示意图：

	a	b	c	f	b	c
a	1	1	1	1	1	1
b	1	2	2	2	2	2
f	1	2	2	3	3	3
c	1	2	3	3	3	4
a	1	2	3	3	3	4
b	1	2	3	3	4	4

可得代码如下：
ZOJ：

#include<iostream>
#include<string>
using namespace std;
int c[1001][1001];
int getc(int i, int j){
	if(i >= 0 && j >= 0)
		return c[i][j];
	else
		return 0;
}

int main(){
	string a, b;
	while(cin >> a >> b){
		for(int i = 0; i < a.length(); ++i){
			for(int j = 0; j < b.length(); ++j){
				if(a[i] == b[j]){
					c[i][j] = getc(i - 1, j - 1) + 1;
				}else{
					c[i][j] = getc(i - 1, j) > getc(i, j - 1) ? getc(i - 1, j) : getc(i, j - 1);
				}
			}
		}
		cout << c[a.length() - 1][b.length() - 1] << endl;
	}
	return 0;
}

NYOJ：

#include<iostream>
#include<string>
using namespace std;
int c[1001][1001];
int getc(int i, int j){
	if(i >= 0 && j >= 0)
		return c[i][j];
	else
		return 0;
}
int main(){
	int n;
	string a, b;
	cin >> n;
	while(n--){
		cin >> a >> b;
		for(int i = 0; i < a.length(); ++i){
			for(int j = 0; j < b.length(); ++j){
				if(a[i] == b[j]){
					c[i][j] = getc(i - 1, j - 1) + 1;
				}else{
					c[i][j] = getc(i - 1, j) > getc(i, j - 1) ? getc(i - 1, j) : getc(i, j - 1);
				}
			}
		}
		cout << c[a.length() - 1][b.length() - 1] << endl;
	}
	return 0;
}

关于为什么我在这道题里似乎多此一举地多给出一个南阳理工学院在线评测系统的来源，是因为它的设计比较不错，有些人可能会说一个ACM在线评测系统并不需要什么好看的界面，重要的是内涵，但作为一个对前端发烧的人来说，它不仅仅只是进行评测，也注重了用户体验，如提交可以直接在问题页面完成，当做比较难的题目时，不需要在题目及提交页面反复切换；代码高亮等等。而且在题目中绞尽脑汁之余，可以看到一个赏心悦目的界面，不也是一件令人放松的事么？而且它也并不缺少内涵，不像其它OJ系统一般，只能看到自己的代码（有的还看不到），通过做题积累NYOJ币，还可以看到别人的最佳解决方案，利于ACMer的学习，更加人性化。

好了，废话不多说，晚安了~

如需转载请注明出处：杰拉斯的博客

杰拉斯的博客