Sequence : Longest Common Subsequence
Longest common subsequence (LCS) of 2 sequences is a subsequence, with maximal length, which is common to both the sequences. O(mn), where m, n = len(s1), len(s2) Dynamic programming: 1) dp[i][j] - length of LCS between s1[0:i] and s2[0:j] 2) dp[0][j] = dp[i][0] = 0 3) if s1[i - 1] == s2[j - 1] : dp[i][j] = dp[i - 1][j - 1] + 1 4) if s1[i - 1] != s2[j - 1] : dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) 5) dp[m][n] - length of LCS between s1 and s2 6) to get LCS traverse dp from dp[m][n] (j = m, j = n) 7) if s1[i - 1] == s2[j - 1] : LCS = s1[i - 1] + LCS, i--, j-- 8) if s1[i - 1] != s2[j - 1] : if dp[i - 1][j] > dp[i][j - 1] : i-- else : j--
|
|
|
// -----------------------------------------------------------------------------
// Longest Common Subsequence C++
// -----------------------------------------------------------------------------
template<typename T>
std::vector<T> LCS(std::vector<T> &s1, std::vector<T> &s2)
{
int m = s1.size();
int n = s2.size();
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));
for (int i = 0; i <= m; i++) dp[i][0] = 0;
for (int j = 0; j <= n; j++) dp[0][j] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i - 1] == s2[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = std::max(dp[i][j - 1],
dp[i - 1][j]);
}
}
int k = dp[m][n];
std::vector<char> lcs(k);
int ix = m, jx = n;
while (ix > 0 && jx > 0) {
if (s1[ix - 1] == s2[jx - 1]) {
lcs[k - 1] = s1[ix - 1];
ix--; jx--; k--;
}
else
if (dp[ix - 1][jx] > dp[ix][jx - 1])
ix--;
else
jx--;
}
return lcs;
}
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
// Longest Common Subsequence C#
// -----------------------------------------------------------------------------
static T[] LCS<T>(T[] s1, T[] s2) where T : IEquatable<T>
{
int m = s1.Length;
int n = s2.Length;
int[][] dp = new int[m + 1][];
for (int i = 0; i < m + 1; i++) dp[i] = new int[n + 1];
for (int i = 0; i <= m; i++) dp[i][0] = 0;
for (int j = 0; j <= n; j++) dp[0][j] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i - 1].Equals(s2[j - 1]))
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = Math.Max(dp[i - 1][j],
dp[i][j - 1]);
}
}
int k = dp[m][n];
T[] lcs = new T[k];
int ix = m, jx = n;
while (ix > 0 && jx > 0) {
if (s1[ix - 1].Equals(s2[jx - 1])) {
lcs[k - 1] = s1[ix - 1];
ix--; jx--; k--;
}
else
if (dp[ix - 1][jx] > dp[ix][jx - 1])
ix--;
else
jx--;
}
return lcs;
}
// -----------------------------------------------------------------------------
# ------------------------------------------------------------------------------
# Longest Common Subsequence Python
# ------------------------------------------------------------------------------
def LCS(s1, s2):
m, n = len(s1), len(s2)
dp = [[0 for j in range(n + 1)] for i in range(m + 1)]
for i in range(m + 1): dp[i][0] = 0
for j in range(n + 1): dp[0][j] = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
k = dp[m][n]
lcs, ix, jx = [0 for i in range(k)], m, n
while ix > 0 and jx > 0:
if s1[ix - 1] == s2[jx - 1]:
lcs[k - 1] = s1[ix - 1]
ix -= 1
jx -= 1
k -= 1
else:
if dp[ix - 1][jx] > dp[ix][jx - 1]:
ix -= 1
else:
jx -= 1
return lcs
# ------------------------------------------------------------------------------