Submission #64264862

---

Source Code Expand

// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
// #include<sys/time.h>
// #include<atcoder/convolution>
// #include<atcoder/modint>


using namespace std;

using P = pair<int, int>;
const int M = 1000000007;
const long long LM = 1LL << 60;


int n, m;
string s, t;
vector<vector<int>> lcslen;
vector<vector<int>> _lcscnt;
vector<vector<int>> nexts, nextt;
// int nexs[26][SIZE], next[26][SIZE];


int lcscnt(int si, int ti) {
    if (lcslen[si][ti] == 0) {
        return 1;
    }
    if (_lcscnt[si][ti] != -1) {
        return _lcscnt[si][ti];
    }
    int res = 0;
    for (int i = 0; i < 26; ++i) {
        int nsi = nexts[i][si] + 1;
        int nti = nextt[i][ti] + 1;
        if (nsi <= n && nti <= m && lcslen[nsi][nti] == lcslen[si][ti] - 1) {
            res += lcscnt(nsi, nti);
            res = min(res, M);
        }
    }
    return _lcscnt[si][ti] = res;
}

void dfs(int si, int ti, int rem, string& ans) {
    if (lcslen[si][ti] == 0) {
        assert(rem == 1);
        return;
    }
    for (int i = 0; i < 26; ++i) {
        int nsi = nexts[i][si] + 1;
        int nti = nextt[i][ti] + 1;
        if (nsi <= n && nti <= m && lcslen[nsi][nti] == lcslen[si][ti] - 1) {
            int c = lcscnt(nsi, nti);
            if (rem > c) {
                rem -= c;
            }
            else {
                ans.push_back((char)('a' + i));
                dfs(nsi, nti, rem, ans);
                return;
            }
        }
    }
    assert(false);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int q;
    cin >> n >> m >> s >> t >> q;

    _lcscnt = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
    lcslen = vector<vector<int>>(n + 1, vector<int>(m + 1));
    nexts = vector<vector<int>>(26, vector<int>(n + 1));
    nextt = vector<vector<int>>(26, vector<int>(m + 1));

    for (int i = 0; i < 26; ++i) {
        nexts[i][n] = n;
        for (int j = n - 1; j >= 0; --j) {
            if (s[j] == 'a' + i)  {
                nexts[i][j] = j;
            }
            else {
                nexts[i][j] = nexts[i][j + 1];
            }
        }
        nextt[i][m] = m;
        for (int j = m - 1; j >= 0; --j) {
            if (t[j] == 'a' + i)  {
                nextt[i][j] = j;
            }
            else {
                nextt[i][j] = nextt[i][j + 1];
            }
        }
    }
    for (int i = n; i >= 0; --i) {
        for (int j = m; j >= 0; --j) {
            if (i < n) {
                lcslen[i][j] = max(lcslen[i][j], lcslen[i + 1][j]);
            }
            if (j < m) {
                lcslen[i][j] = max(lcslen[i][j], lcslen[i][j + 1]);
            }
            if (i < n && j < m) {
                lcslen[i][j] = max(lcslen[i][j], lcslen[i + 1][j + 1] + (s[i] == t[j]));
            }
        }
    }
    int alllcs = lcscnt(0, 0);
    bool zero = true;
    for (int i = 0; i < 26; ++i) {
        if (nexts[i][0] < n && nextt[i][0] < m) {
            zero = false;
        }
    }
    if (zero) {
        alllcs = 0;
    }

    for (int _ = 0; _ < q; ++_) {
        int k;
        cin >> k;
        if (alllcs < k) {
            cout << -1 << '\n';
        }
        else {
            string ans = "";
            dfs(0, 0, k, ans);
            cout << ans << '\n';
        }
    }
    return 0;
}

Submission Info

Judge Result