Create LCSubSequence.cpp

1 files changed, 17 insertions, 0 deletions

diff --git a/string/LCSubSequence.cpp b/string/LCSubSequence.cpp
new file mode 100644
index 0000000..0ea2913
--- /dev/null
+++ b/string/LCSubSequence.cpp
@@ -0,0 +1,17 @@
+string lcss(string &a, string &b) {
+	int m[a.length() + 1][b.length() + 1], x=0, y=0;
+	memset(m, 0, sizeof(m));
+	for(int y = a.length() - 1; y >= 0; y--) {
+		for(int x = b.length() - 1; x >= 0; x--) {
+			if(a[y] == b[x]) m[y][x] = 1 + m[y+1][x+1];
+			else m[y][x] = max(m[y+1][x], m[y][x+1]);
+		}
+	} //for length only: return m[0][0];
+	string res;
+	while(x < b.length() && y < a.length()) {
+		if(a[y] == b[x]) res += a[y++], x++;
+		else if(m[y][x+1] > m[y+1][x+1]) x++;
+		else y++;
+	}
+	return res;
+}