Tag Archives: LCS

HDOJ 1159-Common Subsequence

HDOJ 1159-Common Subsequence
Common Subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 38564 Accepted Submission(s): 17705
Problem Description
A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, ..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, ..., ik> of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. 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
Source
Southeastern Europe 2003


求最长公共子序列。DP模板题,使用一个dp数组即可,用pre记录原来左上角的值。
代码如下,如果要求出一个lcs,参考《算法导论》P225,使用一个二维数组direction记录每个格子最大值来自哪个方向,重构lcs时从右下角不停的往前找。

#include<string>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
int lcs(const string &a, const string &b) {
	int n = a.size(), m = b.size();
	if (n == 0 || m == 0)return 0;
	vector<int> dp(m + 1, 0);
	for (int i = 1; i <= n; ++i) {
		int pre = 0;
		for (int j = 1; j <= m; ++j) {
			int cur = 0;
			if (a[i - 1] == b[j - 1])cur = pre + 1;
			else cur = max(dp[j - 1], dp[j]);
			pre = dp[j];
			dp[j] = cur;
		}
	}
	return dp[m]; // 最大值就是右下角的值
}
void construct_lcs(vector<vector<int>> &direction, const string &a, int i, int j, string &lcs) {
	if (i == 0 || j == 0)return;
	if (direction[i][j] == 3) {
		construct_lcs(direction, a, i - 1, j - 1, lcs);
		lcs += string(1, a[i - 1]); // direction下标1对应a下标0,所以i-1
	}
	else if (direction[i][j] == 2) {
		construct_lcs(direction, a, i - 1, j, lcs);
	}
	else {
		construct_lcs(direction, a, i, j - 1, lcs);
	}
}
string lcs_string(const string &a, const string &b) {
	int n = a.size(), m = b.size();
	if (n == 0 || m == 0)return 0;
	vector<int> dp(m + 1, 0);
	vector<vector<int>> direction(n + 1, vector<int>(m + 1, 0)); // 1:left,2:up,3:diagonal
	for (int i = 1; i <= n; ++i) {
		int pre = 0;
		for (int j = 1; j <= m; ++j) {
			int cur = 0;
			if (a[i - 1] == b[j - 1]) {
				cur = pre + 1;
				direction[i][j] = 3;
			}
			else {
				if (dp[j - 1] > dp[j]) {
					cur = dp[j - 1];
					direction[i][j] = 1;
				}
				else {
					cur = dp[j];
					direction[i][j] = 2;
				}
			}
			pre = dp[j];
			dp[j] = cur;
		}
	}
	string ans;
	construct_lcs(direction, a, n, m, ans); // 从右下角递归往前找,LCRS P225
	return ans;
}
int main() {
	//freopen("input.txt", "r", stdin);
	string a, b;
	while (cin >> a >> b) {
		cout << lcs(a, b) << endl;
		//cout << lcs(a, b) << "\t" << lcs_string(a, b) << endl;;
	}
	return 0;
}

本代码提交AC,用时46MS。

LeetCode Delete Operation for Two Strings

LeetCode Delete Operation for Two Strings
Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.
Example 1:

Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Note:

  1. The length of given words won't exceed 500.
  2. Characters in given words can only be lower-case letters.

给定两个字符串,求最少的删除次数,使得两个字符串相等。
这其实就是求两个字符串的最长公共子序列,因为最少的删除次数之后,两个字符串都变成了lcs,则每个字符串删除的次数就是原始长度减去lcs的长度。
代码如下:

class Solution {
private:
	int lcs(const string& s1, const string& s2) {
		int n1 = s1.size(), n2 = s2.size();
		vector<int> dp1(n2 + 1, 0), dp2(n2 + 1, 0);
		int ans = 0;
		for (int i = 1; i <= n1; ++i) {
			for (int j = 1; j <= n2; ++j) {
				if (s1[i - 1] == s2[j - 1])dp2[j] = dp1[j - 1] + 1;
				else dp2[j] = max(dp1[j], dp2[j - 1]);
				ans = max(ans, dp2[j]);
			}
			dp1.swap(dp2);
		}
		return ans;
	}
public:
	int minDistance(string word1, string word2) {
		int l = lcs(word1, word2);
		return word1.size() - l + word2.size() - l;
	}
};

本代码提交AC,用时52MS。

hihoCoder week 60-1-String Matching Content Length

hihoCoder week 60-1-String Matching Content Length
题目1 : String Matching Content Length
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
We define the matching contents in the strings of strA and strB as common substrings of the two strings. There are two additional restrictions on the common substrings.
The first restriction here is that every common substring's length should not be less than 3. For example:
strA: abcdefghijklmn
strB: ababceghjklmn
The matching contents in strA and strB are substrings ("abc", "jklmn"). Note that though "e" and "gh" are common substrings of strA and strB, they are not matching content because their lengths are less than 3.
The second restriction is that the start indexes of all common substrings should be monotone increasing. For example:
strA: aaabbbbccc
strB: aaacccbbbb
The matching contents in strA and strB are substrings ("aaa", "bbbb"). Note that though "ccc" is common substring of strA and strB and has length not less than 3, the start indexes of ("aaa", "bbbb", "ccc") in strB are (0, 6, 3), which is not monotone increasing.
输入
Two lines. The first line is strA and the second line is strB. Both strA and strB are of length less than 2100.
输出
The maximum length of matching contents (the sum of the lengths of the common substrings).
样例输入
abcdefghijklmn
ababceghjklmn
样例输出
8


本题在普通的最长公共子序列问题上添加了一个限制条件,构成最长公共子序列的每一个子串长度必须大于等于3。题目中下面这段的含义就是指求的是最长公共子序列,LCS就是从左往右依次扫描找相同的字母,ccc是公共子序列,但不是最长的,因为aaabbbb更长。

The matching contents in strA and strB are substrings ("aaa", "bbbb"). Note that though "ccc" is common substring of strA and strB and has length not less than 3, the start indexes of ("aaa", "bbbb", "ccc") in strB are (0, 6, 3), which is not monotone increasing.

至于题解,讨论里写得很清楚了,不过要让我自己想还真想不出来。代码实现也很简单,如下:

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int kMaxLen = 2105;
string a, b;
int dp[kMaxLen][kMaxLen][2];
int f[kMaxLen][kMaxLen];
void Init()
{
	for (int i = 1; i < a.size(); i++)
	{
		for (int j = 1; j < b.size(); j++)
		{
			if (a[i] == b[j])
				f[i][j] = f[i - 1][j - 1] + 1;
			else
				f[i][j] = 0;
		}
	}
}
void Lcs()
{
	for (int i = 1; i < a.size(); i++)
	{
		for (int j = 1; j < b.size(); j++)
		{
			dp[i][j][1] = 0;
			if (f[i][j] >= 3)
			{
				dp[i][j][1] = max(dp[i][j][1], dp[i - 3][j - 3][0] + 3);
				if (f[i][j]>3)
					dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - 1][1] + 1);
			}
			dp[i][j][0] = max(dp[i - 1][j][0], max(dp[i][j - 1][0], dp[i][j][1]));
		}
	}
}
int main()
{
	cin >> a >> b;
	a = " " + a;
	b = " " + b;
	Init();
	Lcs();
	printf("%d\n", dp[a.size() - 1][b.size() - 1][0]);
	return 0;
}

本代码提交AC,用时319MS,内存50MB。