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

重工业，，，

题意简述

给定一个字符串 $S$，再给定 $n_A$ 个 A 类串和 $n_B$ 个 B 类串（均为 $S$ 的字串）。定义 A 类串的权值为该串长，B 类串的权值为 0。

将这些字串抽象为点，给定 $m$ 条 A 类连向 B 类的边。定义一个 B 类串向某个 A 类串连边当且仅当其为该 A 类串的一个前缀。

求一条最长的路径（路径长度定义为路径上经过所有点的权值和），需判断无解。$|S|, n_A, n_B, m\le 2\times 10^5$。

[LOJ 3049]

[Luogu 5284]

主要思路

由于不会 SAM，此处只讲 SA 做法。

假设 $x$ 为 $y$ 的前缀，那么 $x$ 的字典序必定小于 $y$，且 $\operatorname{lcp}(x, y) = |x|$。

于是只需要把 A 串和 B 串一起按字典序排好序，然后对每个 B 串二分一下它为前缀的区间，线段树优化建图，拓扑排序，就喜提 $O(n\log n)$。

怎么按字典序排序？对于俩串，lcp 为较短的，则短的排在长的前面；lcp 比最短的还短，直接按SA::rk[]排即可。

参考代码

注意细节，比如 B 串应该在有相同 A 串时居于前面。

不知道为啥常数巨大，可能我写丑了？

复制

#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
#define FORit(templ, arr, i, a, b) \
for (register templ *i = (arr) + (a), *ed_##i = (arr) + (b) + 1; i != ed_##i; ++i)
#define ROFit(templ, arr, i, a, b) \
for (register templ *i = (arr) + (a), *ed_##i = (arr) + (b)-1; i != ed_##i; --i)
#define GO(x, p, e, i, v) for (register int i = p[x].head, v; i; i = e[i].link)
#define fir first
#define sec second
#define pq priority_queue
#define MP make_pair
typedef long long LL;
typedef double DB;
typedef pair<int, int> PII;
#define Templ(T) template <typename T>
inline int read() {
    reg int ans = 0, f = 1;
    reg char c = getchar();
    while (!isdigit(c)) f ^= (c == '-'), c = getchar();
    for (; isdigit(c); c = getchar()) ans = (ans << 1) + (ans << 3) + (c ^ 48);
    return f ? ans : -ans;
}
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
#define using_mod
const int mod = 998244353;
#ifdef using_mod
inline void inc(int &x, const int &y) { x += y; if (x >= mod) x -= mod; }
inline void dec(int &x, const int &y) { x -= y; if (x < 0) x += mod; }
inline int ksm(int x, LL y) {
    int res = 1;
    for (; y; y >>= 1, x = 1ll * x * x % mod)
        if (y & 1) res = 1ll * res * x % mod;
    return res;
}
#endif
Templ(_Tp) inline _Tp gcd(_Tp x, _Tp y) { return y ? gcd(y, x % y) : x; }
#define FILE(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
#define PBTXDY
} // namespace my_std
using namespace my_std;

const int N = 200010;
int l2g[N];

inline void init(){
    FOR(i, 2, 200000) l2g[i] = l2g[i >> 1] + 1;
}

int n, nA, nB, m;
#define CLR(x) memset(x, 0, sizeof(x))
char str[N];

namespace SA{
int sa[N], rk[N], oldrk[N << 1], cnt[N], px[N], id[N], ht[N];
int st[20][N];
inline int cmp(const int &x, const int &y, const int &w){
    return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
inline void build(){
    CLR(sa), CLR(rk), CLR(oldrk), CLR(cnt), CLR(px), CLR(id);
    CLR(ht), CLR(st);
    Rint m = 127, p, w;
    FOR(i, 1, n) ++cnt[rk[i] = str[i]];
    FOR(i, 1, m) cnt[i] += cnt[i - 1];
    ROF(i, n, 1) sa[cnt[rk[i]]--] = i;
    
    for(w = 1; p < n; w <<= 1, m = p){
        p = 0;
        ROF(i, n, n - w + 1) id[++p] = i;
        FOR(i, 1, n) if(sa[i] > w) id[++p] = sa[i] - w;
        
        memset(cnt, 0, sizeof(cnt));
        FOR(i, 1, n) ++cnt[px[i] = rk[id[i]]];
        FOR(i, 1, m) cnt[i] += cnt[i - 1];
        ROF(i, n, 1) sa[cnt[px[i]]--] = id[i];
        
        p = 0;
        memcpy(oldrk, rk, sizeof(rk));
        FOR(i, 1, n){
            rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
        }
    }
    //build sa[], rk[]
    p = 0;
    FOR(i, 1, n){
        if(p) --p;
        while(str[i + p] == str[sa[rk[i] - 1] + p]) ++p;
        ht[rk[i]] = p;
    }
    //build ht[]
    //ht[i] = lcp(sa[i], sa[i - 1])
    FOR(i, 1, n) st[0][i] = ht[i];
    FOR(i, 1, l2g[n]){
        FOR(j, 1, n - (1 << i) + 1){
            st[i][j] = min(st[i - 1][j],
                st[i - 1][j + (1 << (i - 1))]);
        }
    }
//	FOR(i, 1, n){
//		FOR(j, sa[i], n) putchar(str[j]);
//		putchar('\n');
//	}
}
inline int st_q(Rint x, Rint y){
    Rint k = l2g[y - x + 1];
    y -= (1 << k) - 1;
    return min(st[k][x], st[k][y]);
}
inline int lcp(Rint x, Rint y){
    if(x == y) return n - x + 1;
    x = rk[x], y = rk[y];
    if(x > y) swap(x, y);
    return st_q(x + 1, y);
}
}

struct Sub_str{
    int p, len, id, rk;
    inline bool operator <(const Sub_str &x)const{
        if(SA::lcp(p, x.p) >= min(len, x.len)) return len == x.len ? rk < x.rk : len < x.len;
        else return SA::rk[p] < SA::rk[x.p];
    }
}dt[N << 1];
int a_rk[N], b_l[N], b_r[N], a_p[N], b_id[N], a_len[N];

inline void build_sub(){
    nA = read();
    FOR(i, 1, nA){
        dt[i].p = read();
        a_len[i] = dt[i].len = read() - dt[i].p + 1;
        dt[i].id = i, dt[i].rk = 1;
    }
    nB = read();
    FOR(i, nA + 1, nA + nB){
        dt[i].p = read(), dt[i].len = read() - dt[i].p + 1;
        dt[i].id = i, dt[i].rk = 0;
    }
    // printf("nA, nB: %d, %d\n", nA, nB);
    sort(dt + 1, dt + nA + nB + 1);
    // FOR(i, 1, nA + nB){
        // printf("%d: %c -- ", dt[i].id, dt[i].id <= nA ? 'A' : 'B');
        // FOR(j, dt[i].p, dt[i].p + dt[i].len - 1) putchar(str[j]);
        // putchar('\n');
        // if(dt[i].id > nA){
            // FOR(j, 1, nA + nB){
                // if(i != j && SA::lcp(dt[j].p, dt[i].p) >= dt[i].len) printf("%d ", dt[j].id);
            // }
            // puts("");
        // }
    // }
    Rint cA = nA;
    // dt[nA + nB + 1].rk = dt[nA + nB + 2].rk = cA;
    ROF(i, nA + nB, 1){
        if(dt[i].id <= nA){
            dt[i].rk = a_rk[dt[i].id] = cA--;
        }
        else{
            dt[i].rk = cA;
            // b_l[dt[i].id - nA] = cA + 1;
            // Rint j = i + 1;
            // while(SA::lcp(dt[j].p, dt[i].p) >= dt[i].len) ++j;
            // b_r[dt[i].id - nA] = dt[j - 1].rk;
            // printf("b[%d]: %d -- [%d, %d]\n", dt[i].id, dt[j - 1].id, b_l[dt[i].id - nA], b_r[dt[i].id - nA]);
            b_l[dt[i].id - nA] = cA + 1;
            Rint l = i + 1, r = nA + nB + 1, mid = (l + r) >> 1;
            while(l < r){
                if(SA::lcp(dt[mid].p, dt[i].p) >= dt[i].len){
                    l = mid + 1;
                }
                else r = mid;
                mid = (l + r) >> 1;
            }
            --mid;
            // if(SA::lcp(dt[mid + 1].p, dt[i].p) >= dt[i].len) ++mid;
            // if(SA::lcp(dt[mid].p, dt[i].p) < dt[i].len) --mid;
            b_r[dt[i].id - nA] = dt[mid].rk;
            // printf("b[%d]: %d -- [%d, %d]\n", dt[i].id, dt[mid].id, b_l[dt[i].id - nA], b_r[dt[i].id - nA]);
        }
//		printf("cA: %d\n", cA);
    }
    FOR(i, 1, nA) a_p[a_rk[i]] = i;
    FOR(i, 1, nB) b_id[i] = i + (nA << 2);
//	FOR(i, 1, nA) printf("a_rk[%d] = %d\n", i, a_rk[i]);
//	FOR(i, 1, nB) printf("b(%d): [%d, %d]\n", i, b_l[i], b_r[i]);
}

struct Vertice{
    int head, ind;
    LL val;
};
struct Edge{
    int to, link;
};

namespace GR{
Vertice p[N << 3];
Edge e[N << 4];
int ecnt, tcnt;
int Que[N << 3];
inline void A_E(const int &u, const int &v){
    e[++ecnt] = (Edge){v, p[u].head};
    p[u].head = ecnt, ++p[v].ind;
}
inline void build(const int &t, const int &l, const int &r){
    if(l == r){
        a_rk[a_p[l]] = t;
        p[t].val = a_len[a_p[l]];
        return;
    }
    reg const int mid = (l + r) >> 1;
    build(t << 1, l, mid), build(t << 1 | 1, mid + 1, r);
    A_E(t, t << 1), A_E(t, t << 1 | 1);
}
inline void update(const int &t, const int &l, const int &r,
	const int &L, const int &R, const int &x){
    if(L <= l && r <= R) return A_E(x, t);
    reg const int mid = (l + r) >> 1;
    if(L <= mid) update(t << 1, l, mid, L, R, x);
    if(R > mid) update(t << 1 | 1, mid + 1, r, L, R, x);
}
inline void build(){
    ecnt = 0;
    memset(p, 0, sizeof(p));
    memset(e, 0, sizeof(e));
    build(1, 1, nA);
//	FOR(i, (nA << 2) + 1, (nA << 2) + nB) p[i].val = 1;
    m = read();
    Rint a_, b_;
    FOR(i, 1, m){
        a_ = read(), b_ = read();
        A_E(a_rk[a_], b_id[b_]);
    }
    FOR(i, 1, nB){
        if(b_l[i] <= b_r[i]){
            update(1, 1, nA, b_l[i], b_r[i], (nA << 2) + i);
        }
    }
    tcnt = (nA << 2) + nB;
//	FOR(u, 1, tcnt){
//		printf("p[%d]: %d, %d\ne[%d]: ", u, p[u].val, p[u].ind, u);
//		GO(u, p, e, i, v) printf("%d ", e[i].to);
//		puts("");
//	}
}
inline int Topo_sort(){
    Rint l = 0, r = 0;
    FOR(i, 1, tcnt) if(!p[i].ind) Que[r++] = i;
    while(l < r){
        reg const int u = Que[l++];
        GO(u, p, e, i, v){
            v = e[i].to;
            --p[v].ind;
            if(!p[v].ind) Que[r++] = v;
        }
    }
    return r == tcnt;
}
inline LL dp(){
    reg LL res = 0;
    ROF(i, tcnt - 1, 0){
        reg const int u = Que[i];
        reg LL mx = 0;
        GO(u, p, e, i, v){
            v = e[i].to;
            chkmax(mx, p[v].val);
        }
        p[u].val += mx;
        chkmax(res, p[u].val);
    }
    return res;
}
}

inline void work(){
    scanf("%s", str + 1);
    n = strlen(str + 1);
    // printf("n: %d\n", n);
    SA::build();
    build_sub();
    GR::build();
    if(!GR::Topo_sort()) return puts("-1"), void();
    printf("%lld\n", GR::dp());
}

int main() {
    init();
    int esac = read();
    while(esac--) work();
    return 0;
}