hacktoberfest2020/LCS DP Problem at master · anXcode/hacktoberfest2020 · GitHub

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
using namespace std;

int lcs_mem(string s, string t, int **output) {
	int m = s.size();
	int n = t.size();

	// Base case
	if(s.size() == 0 || t.size() == 0) {
		return 0;
	}

	// Check if ans already exists
	if(output[m][n] != -1) {
		return output[m][n];
	}

	int ans;
	// Recursive calls
	if(s[0] == t[0]) {
		ans = 1 + lcs_mem(s.substr(1), t.substr(1), output);
	}
	else {
		int a = lcs_mem(s.substr(1), t, output);
		int b = lcs_mem(s, t.substr(1), output);
		int c = lcs_mem(s.substr(1), t.substr(1), output);
		ans = max(a, max(b, c));
	}

	// Save your calculation
	output[m][n] = ans;

	// Return ans
	return ans;
}

int lcs_mem(string s, string t) {
	int m = s.size();
	int n = t.size();
	int **output = new int*[m+1];
	for(int i = 0; i <= m; i++) {
		output[i] = new int[n+1];
		for(int j = 0; j <= n; j++) {
			output[i][j] = -1;
		}
	}

	return lcs_mem(s, t, output);
}

int lcs(string s, string t) {
		// Base case
	if(s.size() == 0 || t.size() == 0) {
		return 0;
	}

		// Recursive calls
	if(s[0] == t[0]) {
		return 1 + lcs(s.substr(1), t.substr(1));
	}
	else {

		int a = lcs(s.substr(1), t);
		int b = lcs(s, t.substr(1));
		int c = lcs(s.substr(1), t.substr(1));
		return max(a, max(b, c));
	}
}

int main() {
	string s, t;
	cin >> s >> t;

	cout << lcs_mem(s, t) << endl;
	cout << lcs(s, t) << endl;
}