最長共通部分列

template <typename String>
String lcs(String const& a, String const& b) {
    const int n = a.size(), m = b.size();
    static int X[2048][2048], Y[2048][2048];  // 16MB x 2
    rep(i, n + 1) X[i][0] = 0;
    rep(i, m + 1) Y[0][i] = 0;
    rep(i, n) rep(j, m) {
        if (a[i] == b[j]) {
            X[i + 1][j + 1] = X[i][j] + 1;
            Y[i + 1][j + 1] = 0;
        } else if (X[i + 1][j] < X[i][j + 1]) {
            X[i + 1][j + 1] = X[i][j + 1];
            Y[i + 1][j + 1] = +1;
        } else {
            X[i + 1][j + 1] = X[i + 1][j];
            Y[i + 1][j + 1] = -1;
        }
    }
    String c;
    for (int i = n, j = m; i > 0 && j > 0;) {
        if (Y[i][j] > 0)
            --i;
        else if (Y[i][j] < 0)
            --j;
        else {
            c.push_back(a[i - 1]);
            --i;
            --j;
        }
    }
    reverse(c.begin(), c.end());
    return c;
}