From 6e8adb51706906eb03a8e208b50ee3ac4cbfdf72 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Fri, 24 Feb 2023 17:04:19 +0100 Subject: improved lcss --- string/longestCommonSubsequence.cpp | 20 ++++++++++---------- 1 file changed, 10 insertions(+), 10 deletions(-) (limited to 'string') diff --git a/string/longestCommonSubsequence.cpp b/string/longestCommonSubsequence.cpp index 2a0b74c..109fe72 100644 --- a/string/longestCommonSubsequence.cpp +++ b/string/longestCommonSubsequence.cpp @@ -1,15 +1,15 @@ -string lcss(string& a, string& b) { +string lcss(const string& a, const string& b) { vector> m(sz(a) + 1, vector(sz(b) + 1)); - for(int y = sz(a) - 1; y >= 0; y--) { - for(int x = sz(b) - 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 (int i = sz(a) - 1; i >= 0; i--) { + for (int j = sz(b) - 1; j >= 0; j--) { + if (a[i] == b[j]) m[i][j] = 1 + m[i+1][j+1]; + else m[i][j] = maj(m[i+1][j], m[i][j+1]); }} // Für die Länge: return m[0][0]; - string res; int x = 0, y = 0; - while(x < sz(b) && y < sz(a)) { - if(a[y] == b[x]) res += a[y++], x++; - else if(m[y][x+1] > m[y+1][x+1]) x++; - else y++; + string res; + for (int j = 0, i = 0; j < sz(b) && i < sz(a);) { + if (a[i] == b[j]) res += a[i++], j++; + else if (m[i][j+1] > m[i+1][j]) j++; + else i++; } return res; } -- cgit v1.2.3