A leghosszabb közös részsorozat (LCS) egy olyan probléma, amely két sorozat (vagy sztring) közös részhalmazának legnagyobb hosszúságú, sorrendet megőrző részsorozatát keresi. A részsorozat olyan elemek sorozata, amelyek nem feltétlenül szomszédosak, de a sorrendjük megegyezik az eredeti sorozatokban.
A probléma megoldására a dinamikus programozás technikáját használjuk. Az alapötlet az, hogy egy táblázatban ((dp)) tároljuk az (LCS(X, Y)) értékét, azaz az (X) első (i) karakterének és a (Y) első (j) karakterének leghosszabb közös részsorozatát.
Ha csak a hosszra van szükség, a tárbonyolultság csökkenthető (O(n))-re.
function LCS(X, Y):
m = len(X)
n = len(Y)
dp = * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if X == Y:
dp = dp + 1
else:
dp = max(dp, dp)
# LCS visszafejtése
i, j = m, n
lcs =
while i > 0 and j > 0:
if X == Y:
lcs.append(X)
i -= 1
j -= 1
elif dp > dp:
i -= 1
else:
j -= 1
return ''.join(reversed(lcs))
def lcs(X, Y):
m, n = len(X), len(Y)
dp = * (n + 1) for _ in range(m + 1)]
# Táblázat kitöltése
for i in range(1, m + 1):
for j in range(1, n + 1):
if X == Y:
dp = dp + 1
else:
dp = max(dp, dp)
# LCS visszafejtése
i, j = m, n
lcs =
while i > 0 and j > 0:
if X == Y:
lcs.append(X)
i -= 1
j -= 1
elif dp > dp:
i -= 1
else:
j -= 1
return ''.join(reversed(lcs))
# Példa használat
X = "AGGTAB"
Y = "GXTXAYB"
print("Leghosszabb közös részsorozat:", lcs(X, Y))
Kimenet:
Leghosszabb közös részsorozat: GTAB
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
string lcs(const string& X, const string& Y) {
int m = X.size(), n = Y.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// Táblázat kitöltése
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (X == Y) {
dp = dp + 1;
} else {
dp = max(dp, dp);
}
}
}
// LCS visszafejtése
string lcs = "";
int i = m, j = n;
while (i > 0 && j > 0) {
if (X == Y) {
lcs += X;
--i;
--j;
} else if (dp > dp) {
--i;
} else {
--j;
}
}
reverse(lcs.begin(), lcs.end());
return lcs;
}
int main() {
string X = "AGGTAB";
string Y = "GXTXAYB";
cout << "Leghosszabb közös részsorozat: " << lcs(X, Y) << endl;
return 0;
}
Kimenet:
Leghosszabb közös részsorozat: GTAB
A LCS-algoritmus hatékony és egyszerű módszer a szövegek vagy sorozatok hasonlóságának meghatározására. Bár tárigénye nagyobb, mint egyes alternatív megoldásoké, robusztussága és sokoldalúsága miatt széles körben alkalmazzák a számítástechnikában és a tudományban.