Edit distance: как сжать ДП Левенштейна по памяти до O(min(n,m))?
Расстояние Левенштейна считаю таблицей dp[n+1][m+1]. На больших строках (по 10^5 символов) это 10^10 ячеек — MLE. Сама асимптотика по времени O(n·m) меня устраивает, но память надо урезать. Как?
2 ответа
Каждая строка таблицы зависит только от предыдущей: dp[i][j] использует dp[i-1][j], dp[i][j-1], dp[i-1][j-1]. Значит, достаточно хранить две строки (или одну + одну переменную для диагонали). Бери меньшую размерность как ширину строки — отсюда O(min(n, m)) памяти.
int editDistance(const string& a, const string& b) {
if (a.size() < b.size()) return editDistance(b, a); // b — короче
int n = a.size(), m = b.size();
vector<int> prev(m + 1), cur(m + 1);
for (int j = 0; j <= m; j++) prev[j] = j;
for (int i = 1; i <= n; i++) {
cur[0] = i;
for (int j = 1; j <= m; j++) {
int cost = (a[i-1] == b[j-1]) ? 0 : 1;
cur[j] = min({ prev[j] + 1, cur[j-1] + 1, prev[j-1] + cost });
}
swap(prev, cur);
}
return prev[m];
}
Время O(n·m), память O(min(n,m)). Важно про базу: dp[i][0] = i (удалить i символов) и dp[0][j] = j (вставить j символов). Забыть инициализацию cur[0] = i на каждой строке — классический off-by-one с WA.
Учти: при O(min(n,m)) памяти ты теряешь возможность восстановить саму последовательность операций (трасса требует всю таблицу). Если нужна и трасса, и память — берут алгоритм Хиршберга: divide-and-conquer по середине строки с двумя проходами «вперёд» и «назад», что даёт O(n·m) времени и O(min(n,m)) памяти даже с восстановлением. Но если нужно только число — двух строк достаточно.