From f1d5de7e374c215ce3da513d1dc3bb2577c1dc3e Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Mon, 10 Oct 2016 21:40:43 +0200 Subject: Typesetting string section. --- string/longestCommonSubsequence.cpp | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) create mode 100644 string/longestCommonSubsequence.cpp (limited to 'string/longestCommonSubsequence.cpp') diff --git a/string/longestCommonSubsequence.cpp b/string/longestCommonSubsequence.cpp new file mode 100644 index 0000000..7bcf851 --- /dev/null +++ b/string/longestCommonSubsequence.cpp @@ -0,0 +1,17 @@ +// Laufzeit: O(|a|*|b|) +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]); + }} // Für die Länge: 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; +} -- cgit v1.2.3