forked from timoncui/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLongest_Common_Subsequence.cpp
More file actions
51 lines (41 loc) · 1.38 KB
/
Longest_Common_Subsequence.cpp
File metadata and controls
51 lines (41 loc) · 1.38 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
Author: Timon Cui, [email protected]
Title: Longest Common Subsequence
Description:
You will be given two lines. The first line will contain the string A,
the second line will contain the string B.
Both strings consist of no more than 50000 lowercase Latin letters.
Output the length of the longest common subsequence of strings A and B.
Difficulty rating: Medium
Source:
http://www.spoj.pl/problems/EELCS/ "Easy"
http://www.spoj.pl/problems/LCS0/ "Hard"
Notes:
O(MN) time and O(N) space.
This passes the "Easy" version but fails the "Hard" version due to high time complexity.
More time efficient algorithms exist:
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=878178
*/
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int longestCommonSubsequence(const string& a, const string& b) {
int A = a.size(), B = b.size();
int L[2][B + 1];
for (int i = 0; i <= 1; ++i) L[i][0] = 0;
for (int i = 0; i <= B; ++i) L[0][i] = 0;
for (int i = 1; i <= A; ++i) {
int this_i = i % 2, pre_i = this_i ? 0 : 1;
for (int j = 1; j <= B; ++j) {
if (a[i - 1] == b[j - 1]) L[this_i][j] = 1 + L[pre_i][j - 1];
else L[this_i][j] = max(L[pre_i][j], L[this_i][j - 1]);
}
}
return max(L[0][B], L[1][B]);
}
int main() {
string a, b;
cin >> a >> b;
cout << longestCommonSubsequence(a, b);
}