OI题解 - 字符串问题(LOJ) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI题解 - 字符串问题(LOJ)

发表于 Valine：

马上要省选了啊

# 题面

LOJ 3049

# 解析

先考虑暴力的做法，我们可以想到一个DP——$f_i$ 表示当前的字符串 $T$ 以第 $i$ 个A串结尾，$|T|$ 的最大值。

然后转移就找到 $A_i$ 支配的一个 B串 $B_j$；再枚举 $A_k$，如果 $B_j$ 是 $A_k$ 的前缀，那么就可以从 $f_i$ 转移到 $f_k$ 了——$f_k=\max\{f_k,f_i+|A_k|\}$。

如何判是不是可以无限循环？那么可以想到把转移边看成有向边，然后用拓扑跑一次DP，就可以在计算DP值的同时判断是否有环了；如果有环，因为转移边的权值 $|A_k|$ 都是正数，所以出现环就说明可以无限循环。

但是非常明显的，这样建图有 $n^2$ 条边。

看到“前缀”，我们可以把串整个倒过来就成了“后缀”，于是可以建SAM！如果 SAM 上代表串 $B_j$ 的节点是 $Q_j$，那么以 $B_j$ 为前缀（即倒转后以 $B_j$ 为后缀）的串就是 parent 树上 $Q_j$ 的后代节点代表的串。

于是考虑这样优化建图：对于每一个 $A_i$，记 SAM 上对应的节点为 $P_i$，同时新建一个节点 $T_i$；对于每一个 $B_i$ 记 SAM 上对应的节点为 $Q_i$。

  1. parent 树上定义树边的方向为“从父亲指向儿子”，这样就能从 $Q_i$ 走到以 $B_j$ 为前缀的串了；
  2. $P_i$ 向 $T_i$ 连边，即表示把 $A_i$ 接在当前串的末尾；
  3. 如果 $A_i$ 支配 $B_j$ 则 $T_i$ 向 $Q_j$ 连边，即借助 $B_j$ 找到下一个A串；

DP仍然是拓扑DP，每到达 $T_i$ 点，DP值就增加 $|A_i|$。

这样DP看起来正确，其实错的也很显然，因为 SAM 的一个节点代表了多个长度连续的字符串。于是如果一个点可以代表多个A串或B串，则需把它拆成长度递增的一条链——使得拆点之后，每个点要么不代表AB串，要么只代表一个本质不同的AB串（如果两个串长得一模一样，当然可以用同一个点代表）。

这样就没有任何问题了……就是记得多测要清空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
/*Lucky_Glass*/
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 2e5 + 10;

inline int Ri() {
    register int a = 0, c = getchar();
    while (c < '0' || '9' < c) c = getchar();
    while ('0' <= c && c <= '9') a = (a << 1) + (a << 3) + c - '0', c = getchar();
    return a;
}

struct SAM {
    struct NODE {
        int nxt[26], lnk, len;
        int &operator[](const int &c) { return nxt[c]; }
    } nod[N << 1];
    int ncnt, lst, ton[N << 1], sot[N << 1], anc[N << 1][20];
    void Init() {
        ncnt = lst = 1;
        nod[1] = nod[0], nod[1].lnk = -1;
    }
    int NewNode() {
        int p = ++ncnt;
        nod[p] = nod[0];
        return p;
    }
    int Expand(const int &c) {
        int cur = NewNode(), p = lst;
        lst = cur;
        nod[cur].len = nod[p].len + 1;
        while ((~p) && !nod[p][c]) nod[p][c] = cur, p = nod[p].lnk;
        if (~p) {
            int q = nod[p][c];
            if (nod[q].len == nod[p].len + 1)
                nod[cur].lnk = q;
            else {
                int nq = NewNode();
                nod[nq] = nod[q], nod[nq].len = nod[p].len + 1;
                nod[cur].lnk = nod[q].lnk = nq;
                while ((~p) && nod[p][c] == q) nod[p][c] = nq, p = nod[p].lnk;
            }
        } else
            nod[cur].lnk = 1;
        return cur;
    }
    void IniAnc(int len) {
        memset(ton, 0, sizeof ton);
        memset(anc, 0, sizeof anc);
        for (int i = 1; i <= ncnt; i++) ton[nod[i].len]++;
        for (int i = 1; i <= len; i++) ton[i] += ton[i - 1];
        for (int i = 1; i <= ncnt; i++) sot[ton[nod[i].len]--] = i;
        for (int it = 1; it <= ncnt; it++) {
            int i = sot[it];
            anc[i][0] = nod[i].lnk;
            for (int j = 1; j < 20; j++) anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
    int Search(int u, int len) {
        for (int i = 19; i >= 0; i--)
            if (nod[anc[u][i]].len >= len)
                u = anc[u][i];
        return u;
    }
} Sa;

struct GRAPH {
    int head[N * 5], du[N * 5], nxt[N * 8], to[N * 8], ncnt;
    void AddEdge(int u, int v) {
        //		printf("+ %d %d\n",u,v);
        int p = ++ncnt;
        nxt[p] = head[v], to[p] = u, head[v] = p;
        du[u]++;
    }
    void Init(int siz) {
        for (int i = 0; i <= siz; i++) head[i] = du[i] = 0;
        ncnt = 0;
    }
    int operator[](const int &u) { return head[u]; }
} Gr;

char str[N];
int nA, nB, n, m, mcnt, ed[N];
int rem[N << 1], rlen[N << 1];
int sotA[N], sotB[N];
long long dp[N * 5];

struct RANG {
    int le, ri, lo;
    inline void Read() {
        le = Ri(), ri = Ri();
        lo = Sa.Search(ed[le], ri - le + 1);
    }
    inline int Len() { return ri - le + 1; }
};
RANG Ra[N], Rb[N];

bool cmpA(const int &a, const int &b) { return Ra[a].Len() > Ra[b].Len(); }
bool cmpB(const int &a, const int &b) { return Rb[a].Len() > Rb[b].Len(); }
void Match(RANG &A) {
    int org = A.lo;
    if (rlen[org] == A.Len())
        A.lo = rem[org];
    else {
        mcnt++;
        rlen[org] = A.Len();
        Gr.AddEdge(mcnt, rem[org]);
        rem[org] = mcnt;
        A.lo = mcnt;
    }
}
queue<int> que;
int main() {
    //	freopen("input.txt","r",stdin);
    for (int cas = Ri(); cas; cas--) {
        // Read & Init SAM
        scanf("%s", str + 1);
        n = strlen(str + 1);
        Sa.Init();
        for (int i = n; i >= 1; i--) ed[i] = Sa.Expand(str[i] - 'a');
        Sa.IniAnc(n);
        nA = Ri();
        for (int i = 1; i <= nA; i++) Ra[i].Read(), sotA[i] = i;
        nB = Ri();
        for (int i = 1; i <= nB; i++) Rb[i].Read(), sotB[i] = i;
        // Rebuild Tree
        for (int i = 1; i <= Sa.ncnt; i++) rem[i] = i, rlen[i] = Sa.nod[i].len;
        sort(sotA + 1, sotA + nA + 1, cmpA);
        sort(sotB + 1, sotB + nB + 1, cmpB);
        int pA = 1, pB = 1, qA = sotA[pA], qB = sotB[pB];
        mcnt = Sa.ncnt;
        while (pA <= nA && pB <= nB) {
            if (Ra[qA].Len() >= Rb[qB].Len())
                Match(Ra[qA]), qA = sotA[++pA];
            else
                Match(Rb[qB]), qB = sotB[++pB];
        }
        while (pA <= nA) Match(Ra[qA]), qA = sotA[++pA];
        while (pB <= nB) Match(Rb[qB]), qB = sotB[++pB];
        for (int i = 2; i <= Sa.ncnt; i++) Gr.AddEdge(Sa.nod[i].lnk, rem[i]);
        // Build Graph
        for (int i = 1; i <= nA; i++) Gr.AddEdge(Ra[i].lo, mcnt + i), dp[Ra[i].lo] = Ra[i].Len();
        m = Ri();
        for (int i = 1; i <= m; i++) {
            int A = Ri(), B = Ri();
            Gr.AddEdge(mcnt + A, Rb[B].lo);
        }
        // Run
        for (int i = 1; i <= mcnt + nA; i++)
            if (!Gr.du[i])
                que.push(i);
        int cir = mcnt + nA;
        long long ans = 0;
        while (!que.empty()) {
            cir--;
            int u = que.front();
            que.pop();
            ans = max(ans, dp[u]);
            for (int it = Gr[u]; it; it = Gr.nxt[it]) {
                int v = Gr.to[it];
                if (v <= mcnt)
                    dp[v] = max(dp[v], dp[u]);
                else
                    dp[v] = max(dp[v], dp[u] + Ra[v - mcnt].Len());
                Gr.du[v]--;
                if (!Gr.du[v])
                    que.push(v);
            }
        }
        if (cir)
            printf("-1\n");
        else
            printf("%lld\n", ans);
        // Clear
        Gr.Init(mcnt + nA);
        for (int i = 1; i <= mcnt + nA; i++) dp[i] = 0;
    }
    return 0;
}

THE END

Thanks for reading!