「十二省联考 2019」字符串问题题解

2020-02-04

谨以此题纪念自己颓废的, 什么都不会的高一 (bushi

题目链接: https://www.luogu.com.cn/problem/P5284

SAM 优化建图 + 拓扑排序求最长路.

写这道题啊, 只是感到自己的高一很可笑吧, 连题意都不大能读清, 正解的算法听都没有听过, 输出样例就弃疗离场.

题目思路

考虑目标串 $T$ 的构造过程, 可以发现 $A, B$ 串可以视为节点, 支配关系和前缀可以看作边, $T$ 就对应图中一条路径, 那么把图建出来跑最长路就好了.

另外可以发现, 如果图上存在环就说明可以构造出无限长的串 $T$, 输出 -1, 否则这就是个 DAG, 最长路跑拓扑排序就好了.

进一步考虑建边

$A_{id_i} \rightarrow B$

支配关系是题目给出的, 直接把 $A, B$ 串对应节点连起来就好了.
$B_j \rightarrow A_i$, 其中 $B_j$ 为 $A_i$ 的前缀

这里就有些意思了, ~~如果直接暴力建边就可以拿到 10 pts 的好成绩~~

考虑前缀, 就是反串的后缀, 我们可以想到对 $S$ 的反串建出 SAM, 把串 $A, B$ 放到 SAM 上匹配, 这一步可以套路地用倍增解决. 假设匹配到 SAM 上的节点 $u$, 那么就新建一个节点 $v$ 表示当前匹配串, 点权为匹配串长度, 并把 $v$ 挂在 $u$ 上.

对于 SAM 上的一个节点 $u$, ~~上面挂这一堆节点表示 A, B 串~~, 我们将这些节点以点权为第一关键字, 是否为 $B$ 串为第二关键字从小到大排序, 并根据这个顺序依次连边.

另外还需考虑 SAM 上节点 $u$ 和后缀链接 $\text{lnk}(u)$ 的关系, 对于反串中的前缀, 存在一个前缀是另一前缀的前缀, 那么就是从 $\text{lnk}(u)$ 向 $u$ 连边了. 当然, 由于上一步的连边此处 $\text{lnk}(u)$ 的实际节点稍有不同.

~~具体实现代码里很清晰, 正确性很显然~~

代码实现

细节不多的题还是好码一点的.
~~这就是你抄题解还 WA 了一发的原因了 ?~~ (

// Luogu P5284
// DeP
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int MAXN = 2e5+5, LOG = 20, MAXV = MAXN << 2, MAXE = MAXN * 5;

int n, m, na, nb, uidx;
char S[MAXN];
bool isA[MAXV];
int Aidx[MAXN], Bidx[MAXN], lst[MAXN << 1], pos[MAXN], pre[LOG][MAXN << 1], len[MAXV];
vector<int> G[MAXN << 1];

namespace SAM {
    const int MAXN = ::MAXN << 1, SIGMA = 26;
    int ch[MAXN][SIGMA], lnk[MAXN], nidx, last;
    
    inline void init() {
        last = nidx = 1;
        memset(ch[1], 0, sizeof ch[1]);
    }
    inline int newnode(int l) {
        len[++nidx] = l, lnk[nidx] = 0;
        memset(ch[nidx], 0, sizeof ch[nidx]);
        return nidx;
    }

    void insert(int val) {
        int nd = newnode(len[last] + 1), p = last;
        while (p && !ch[p][val]) ch[p][val] = nd, p = lnk[p];
        if (!p) lnk[nd] = 1;
        else {
            int q = ch[p][val];
            if (len[q] == len[p] + 1) lnk[nd] = q;
            else {
                int nxt = newnode(len[p] + 1);
                lnk[nxt] = lnk[q];
                memcpy(ch[nxt], ch[q], sizeof ch[nxt]);
                while (p && ch[p][val] == q) ch[p][val] = nxt, p = lnk[p];
                lnk[q] = lnk[nd] = nxt;
            }
        }
        last = nd;
    }
}

namespace Graph {
    struct Edge { int nxt, to; } edges[MAXE];
    int head[MAXV], eidx, in[MAXV];

    inline void init() {
        memset(in, 0, sizeof in);
        memset(head, -1, sizeof head), eidx = 1;
    }
    inline void AddEdge(int from, int to) {
        ++in[to];
        edges[++eidx] = (Edge){ head[from], to };
        head[from] = eidx;
    }

    LL Toposort() {
        static LL f[MAXV];
        queue<int> Q;
        for (int i = 1; i <= uidx; ++i) {
            f[i] = 0;
            if (!in[i]) Q.push(i);
        }
        LL ans = 0;
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            ans = max(ans, f[u] + len[u]);
            for (int i = head[u]; ~i; i = edges[i].nxt) {
                int v = edges[i].to;
                f[v] = max(f[v], f[u] + len[u]);
                if (!(--in[v])) Q.push(v);
            }
        }
        for (int i = 1; i <= uidx; ++i)
            if (in[i]) return -1;
        return ans;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    int Ti;
    scanf("%d", &Ti);
    while (Ti--) {
        // init
        SAM::init(), Graph::init();
        memset(isA, false, sizeof isA);
        // input
        scanf("%s", S+1);
        // build SAM
        n = (int) strlen(S+1);
        for (int i = n; i; --i)
            SAM::insert(S[i] - 'a'), pos[i] = SAM::last;
        for (int i = 1; i <= SAM::nidx; ++i)
            pre[0][i] = SAM::lnk[i], G[i].clear();
        for (int j = 1; j < LOG; ++j)
            for (int i = 1; i <= SAM::nidx; ++i) pre[j][i] = pre[j-1][pre[j-1][i]];
        // find A in SAM
        scanf("%d", &na);
        uidx = SAM::nidx;
        for (int L, R, i = 1; i <= na; ++i) {
            scanf("%d%d", &L, &R);
            int lgt = R - L + 1, u = pos[L];
            for (int j = LOG-1; j >= 0; --j)
                if (pre[j][u] && len[pre[j][u]] >= lgt) u = pre[j][u];
            len[++uidx] = lgt, Aidx[i] = uidx, isA[uidx] = true;
            G[u].push_back(uidx);
        }
        // find B in SAM
        scanf("%d", &nb);
        for (int L, R, i = 1; i <= nb; ++i) {
            scanf("%d%d", &L, &R);
            int lgt = R - L + 1, u = pos[L];
            for (int j = LOG-1; j >= 0; --j)
                if (pre[j][u] && len[pre[j][u]] >= lgt) u = pre[j][u];
            len[++uidx] = lgt, Bidx[i] = uidx;
            G[u].push_back(uidx);
        }
        // link edges in SAM
        for (int v, u = 1; u <= SAM::nidx; ++u) {
            int last = u;
            sort(G[u].begin(), G[u].end(),
                    [](const int& a, const int& b){ return len[a] < len[b] || (len[a] == len[b] && isA[a] < isA[b]); });
            for (size_t i = 0; i < G[u].size(); ++i) {
                Graph::AddEdge(last, v = G[u][i]);
                if (!isA[v]) last = v;
            }
            lst[u] = last;
        }
        for (int i = 2; i <= SAM::nidx; ++i)
            Graph::AddEdge(lst[SAM::lnk[i]], i);
        // clean unexisted value
        for (int u = 1; u <= uidx; ++u)
            if (!isA[u]) len[u] = 0;
        // link A, B
        scanf("%d", &m);
        for (int u, v, i = 1; i <= m; ++i)
            scanf("%d%d", &u, &v), Graph::AddEdge(Aidx[u], Bidx[v]);
        // solve & output
        printf("%lld\n", Graph::Toposort());
    }
    return 0;
}

DepletedPrism's Blog

「十二省联考 2019」字符串问题 题解

题目思路

代码实现

「十二省联考 2019」字符串问题题解