「洛谷 P4341」外星联络 - Trie

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

小 P 在看过电影《超时空接触》(Contact)之后被深深的打动，决心致力于寻找外星人的事业。于是，他每天晚上都爬在屋顶上试图用自己的收音机收听外星人发来的信息。

虽然他收听到的仅仅是一些噪声，但是他还是按照这些噪声的高低电平将接收到的信号改写为由 0 和 1 构成的串， 并坚信外星人的信息就隐藏在其中。他认为，外星人发来的信息一定会在他接受到的 01 串中重复出现，所以他希望找到他接受到的 01 串中所有重复出现次数大于 \(1\) 的子串。

但是他收到的信号串实在是太长了，于是，他希望你能编一个程序来帮助他。

对于 \(100\%\) 的数据，满足 \(0 \le N \le 3000\)

解题思路

这个数据范围就限制了最高复杂度为 \(O(n^2)\)。

对于所有子串，我们可以建立一颗 Trie。设字符串开头为 \(1\)，插入开头为 \(1\)、\(2\)、\(3\)、\(\cdots\)、\(n\)，结尾均为 \(n\) 的子串。然后从根遍历就可得到所有的子串。然后从根 DFS 统计即可得到答案。

对于字典序，我们可以先 DFS \(0\) 节点，再 DFS \(1\) 节点。

代码演示

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
#include <cstdio>

const int MAXN = 3000;

int trie[MAXN * MAXN + 2][2], tot = 1;
int end[MAXN * MAXN + 2];

inline void insert(char *str, int len) {
    int p = 1;
    for (int i = 0; i < len; i++) {
        int ch = str[i] - '0';
        if (trie[p][ch] == 0) trie[p][ch] = ++tot;
        p = trie[p][ch];
        end[p]++;
    }
}

void dfs(int p) {
    if (end[p] > 1) printf("%d\n", end[p]);
    if (trie[p][0]) dfs(trie[p][0]);
    if (trie[p][1]) dfs(trie[p][1]);
}

int main() {
    int n;
    static char str[MAXN + 1];

    scanf("%d", &n);
    scanf("%s", str);

    for (int i = 0; i < n; i++) {
        insert(str + i, n - i);
    }

    dfs(1);

    return 0;
}