LCS за O(n·m): как восстановить саму подпоследовательность, а не длину?
Наибольшую общую подпоследовательность двух строк (LCS) считаю таблицей dp[i][j], длину получаю. Но надо вывести саму LCS. Как пройти по таблице обратно и собрать символы, ничего не перепутав?
2 ответа
Сначала строим полную таблицу dp, затем идём из правого нижнего угла обратно. Если символы совпали (a[i-1]==b[j-1]) — этот символ входит в LCS, идём по диагонали (i-1,j-1). Иначе двигаемся туда, откуда пришёл максимум: вверх (i-1,j) или влево (i,j-1).
int n = a.size(), m = b.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = (a[i-1] == b[j-1]) ? dp[i-1][j-1] + 1
: max(dp[i-1][j], dp[i][j-1]);
string lcs;
int i = n, j = m;
while (i > 0 && j > 0) {
if (a[i-1] == b[j-1]) { lcs += a[i-1]; i--; j--; }
else if (dp[i-1][j] >= dp[i][j-1]) i--;
else j--;
}
reverse(lcs.begin(), lcs.end());
Сложность O(n·m) время и память. Грабли: символы собираются с конца, поэтому в конце reverse. И база dp[0][*]=dp[*][0]=0 обязательна (пустая строка даёт LCS длины 0) — её удобно задать инициализацией вектора нулями.
Если нужна только длина LCS (без восстановления), память можно урезать до O(min(n,m)) двумя строками, как в edit distance — но тогда трассу не восстановишь. Ещё нюанс: LCS ≠ longest common substring (непрерывная подстрока). Для substring рекуррентность другая: dp[i][j] = (a[i-1]==b[j-1]) ? dp[i-1][j-1]+1 : 0, и ответ — максимум по всей таблице, а не dp[n][m]. Их часто путают по названию и ловят WA.