DDOSvoid's Blog

The 16th Heilongjiang Provincial Collegiate Programming Contest E Elastic Search

发表于 更新于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

题目描述

http://codeforces.com/gym/103107/problem/E

简要题意：给定 $n$ 个字符串，如果串 $t$ 是 $s$，则连一条 $t$ 到 $s$ 的有向边，求这个 $DAG$​ 的最长路

$n\le 5\times 10^5,len\le 5\times 10^5$

Solution

建出 $AC$ 自动机后对于每个串的每个前缀求出匹配点连边，然后 $AC$ 自动机上的点按照 $fail$ 树连有向边

然后直接在 $DAG$ 上求最长路即可

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
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#define maxn 500010
using namespace std;

int n, l[maxn], r[maxn];

char s[maxn];

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn], in[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; ++in[v];
    e[c1].next = head[u]; head[u] = c1++;
}

#define ch s[i] - 'a'
struct AC_automaton {
    int nxt[26], v, fail;
} T[maxn]; int top = 1, rt = 1, id[maxn];
int insert(char *s) {
    int now = rt, l = strlen(s);
    for (int i = 0; i < l; ++i) {
        if (!T[now].nxt[ch]) T[now].nxt[ch] = ++top;
        now = T[now].nxt[ch];
    } ++T[now].v;
    return now;
} 

void init_fail() {
    queue<int> Q; 
    for (int i = 0; i < 26; ++i) {
        int &u = T[rt].nxt[i];
        if (!u) { u = rt; continue; }
        T[u].fail = rt; Q.push(u); 
    }
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); 
        for (int i = 0; i < 26; ++i) {
            int &v = T[u].nxt[i];
            if (!v) { v = T[T[u].fail].nxt[i]; continue; }
            T[v].fail = T[T[u].fail].nxt[i]; Q.push(v);
        }
    }
    for (int i = 2; i <= top; ++i) add_edge(T[i].fail, i);
}

int f[maxn];
void topsort() {
    queue<int> Q;
    for (int i = 1; i <= top; ++i)
        if (!in[i]) Q.push(i);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); f[u] += T[u].v;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to; f[v] = max(f[v], f[u]);
            if (--in[v] == 0) Q.push(v);
        }
    }
}

int use[maxn];
int main() { fill(head, head + maxn, -1);
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        l[i] = r[i - 1] + 1; 
        cin >> s + l[i];
        r[i] = l[i] + strlen(s + l[i]) - 1; 
        id[i] = insert(s + l[i]);
    } init_fail();
    for (int i = 1; i <= n; ++i) { 
        if (use[id[i]]) continue; use[id[i]] = 1; 
        int now = rt;
        for (int j = l[i]; j <= r[i]; ++j) { 
            now = T[now].nxt[s[j] - 'a'];
            if (id[i] != now) add_edge(now, id[i]); 
        }
    } topsort(); 
    cout << *max_element(f + 1, f + top + 1) << "\n";
    return 0;
}