# LeetCode Longest Common Subsequence

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.


Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.


Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.


Constraints:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000
• The input strings consist of lowercase English characters only.

class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
int a = dp[i - 1][j], b = dp[i][j - 1], c = dp[i - 1][j - 1];
if (text1[i - 1] == text2[j - 1])++c;
dp[i][j] = max(max(a, b), c);
}
}
return dp[m][n];
}
};


# 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): 59402    Accepted Submission(s): 27503

Problem DescriptionA 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
0

SourceSoutheastern Europe 2003
RecommendIgnatius   |   We have carefully selected several similar problems for you:  10871176100310581069

#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;
}

# 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.

# 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

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.