TIOJ 2010：最長共同子序列（LCS）

TIOJ 2010：最長共同子序列（LCS）

題目大意：給兩個長度為 $n, m\leq 10^4$ 的字串 $a, b$，請你輸出他們的 $\text{LCS}$。

解法：這題的記憶體限制很小，所以沒辦法用空間 $O(n^2)$ 的作法，注意到如果只是要算長度多長，可以用滾動的算出，空間複雜度 $O(n)$，那有一個分治的作法，可以把 $a$ 分成前後兩段，去跟 $b$ 算前綴 $\text{LCS}$ 跟後綴 $\text{LCS}$ 的長度，找出總和最大的地方，就可以分成前半段跟後半段繼續遞迴，時間複雜度 $O(n^2)$，空間複雜度 $O(n)$。

$\text{Code：}$

#include <stdio.h>
#include <string.h>
#include <algorithm>

const int N = 1e4 + 5;

int n, m, sz;
int f[2][N], g[2][N];
char a[N], b[N], ans[N];

inline void Set (int i, char c) {
    sz = std::max (sz, i);
    ans[i - 1] = c;
}

void divide (int u, int d, int l, int r, int sum) {
    if (u > d || l > r) return;
    if (u == d) {
        for (int i = l; i <= r; i++) if (a[u] == b[i]) {
            Set (sum + 1, a[u]);
            return;
        }
        return;
    }
    int mid = (u + d) / 2, len = r - l + 1;
    bool ff = 0, gg = 0;
    std::fill (f[ff], f[ff] + len + 2, 0);
    std::fill (f[!ff], f[!ff] + len + 2, 0);
    for (int i = u; i <= mid; i++) {
        ff ^= 1;
        for (int j = 1; j <= len; j++) {
            if (a[i] == b[j + l - 1]) f[ff][j] = f[!ff][j - 1] + 1;
            else f[ff][j] = std::max (f[ff][j - 1], f[!ff][j]);
        }
    }
    std::fill (g[gg], g[gg] + len + 2, 0);
    std::fill (g[!gg], g[!gg] + len + 2, 0);
    for (int i = d; i > mid; i--) {
        gg ^= 1;
        for (int j = len; j >= 1; j--) {
            if (a[i] == b[j + l - 1]) g[gg][j] = g[!gg][j + 1] + 1;
            else g[gg][j] = std::max (g[gg][j + 1], g[!gg][j]);
        }
    }
    int mx = -1, p;
    for (int i = 0; i <= len; i++) if (f[ff][i] + g[gg][i + 1] > mx) {
        mx = f[ff][i] + g[gg][i + 1];
        p = i;
    }
    if (mx == -1) return;
    bool isl = 0, isr = 0;
    if (f[ff][p] != 0) isl = 1;
    if (g[gg][p + 1] != 0) isr = 1;
    len = f[ff][p];
    if (isl) divide (u, mid, l, l + p - 1, sum);
    if (isr) divide (mid + 1, d, l + p, r, sum + len);
}

int main() {
    int tt;
    scanf ("%d", &tt);
    while (tt--) {
        scanf ("%d %d", &n, &m);
        scanf ("%s", a + 1);
        scanf ("%s", b + 1);
        if (strcmp (a + 1, b + 1) == 0) {
            printf ("%s\n", a + 1);
            continue;
        }
        sz = 0;
        divide (1, n, 1, m, 0);
        if (sz == 0) {
            printf ("*\n");
            continue;
        }
        ans[sz] = '\0';
        printf ("%s\n", ans);
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！