【算法】Trie图

引言

Trie图是Trie树的变种，结合了ac自动机中的思想。

而ac自动机的根本思想是基于kmp的next数组构建的fail指针。

所以，在学习Trie图前，请先搞清楚kmp算法。

关于AC自动机

我太久没写过AC自动机了，只知道AC自动机可以自动ac了。

所以，我还真的说不出AC自动机和我写的trie图有什么区别，可能我写的就叫ac自动机吧。

或者说，可能AC自动机和Trie图本来就是几乎一样的。

Trie图

关于Trie图，只要找到有图（那种非常好看的图）的那种博文，一般讲的都比较清楚。

因为，根本不用看字，看看图就明白了。

这里推荐一个博客：http://www.cnblogs.com/gtarcoder/p/4820560.html

Trie图写起来非常短，我这种邋遢的代码风格也就10行。

先上代码：

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
struct TR {
    int son[26];
    int f;
    bool fg;
}tr[M];

void insert(char *str) {
    int len = strlen(str);
    int now = 1; // root
    for (int i = 0, x; i < len; i++) {
        x = str[i] - 'a';
        if (!tr[now].son[x]) tr[now].son[x] = ++cnt;
        now = tr[now].son[x];
    }
    tr[now].fg = true;
}

void build_trie() {
    int h = 1, t = 2, sta, ch, fl;
    q[1] = 1; // root
    while (h < t) {
        sta = q[h++];
        for (int i = 0; i < 26; i++) {
            ch = tr[sta].son[i];
            if (sta == 1) fl = 1;
            else fl = tr[tr[sta].f].son[i];
            if (!ch) tr[sta].son[i] = fl;
            else {
                tr[ch].f = fl;
                tr[ch].fg |= tr[fl].fg;
                q[t++] = ch;
            }
        }
    }
}
  • trie图中同样有失败指针，即以上代码中的f
  • trie图中和trie树一样，用fg标记单词的结束字符
  • trie图比较好的地方在于，对于trie树中为空的孩子节点，它将这个孩子节点直接指向了失败指针的孩子节点，这个节点必然不会是空节点（除了是根节点的情况）。这里非常值得注意的是，这个孩子节点其实跨越了很多失败指针的，也就相当于将失败指针类似于并查集那样压缩。之所以会这样，是因为，当前节点的失败指针指向的节点可能也没有这个孩子，所以就要不停的调用失败指针，直到有找到有这个孩子的失败指针为止（或者到根节点为止）。

应用

字符串匹配

HDU 2222，多么好的题号～

字符串匹配模板题：

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
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>

using namespace std;

#define N 10010
#define M 1000010

struct TR {
    int son[26];
    int f;
    bool fg;// 为了保留Trie的原始形态，此处保留了fg，否则可以删除
    int ct;
}tr[M];

char a[M * 100];
int cnt;
int ans, n, cas;
int q[M * 4];

void insert(char *str) {
    int len = strlen(str);
    int now = 1; // root
    for (int i = 0, x; i < len; i++) {
        x = str[i] - 'a';
        if (!tr[now].son[x]) tr[now].son[x] = ++cnt;
        now = tr[now].son[x];
    }
    tr[now].fg = true;
    tr[now].ct++; //相同单词算两个
}

void build_trie() {
    int h = 1, t = 2, sta, ch, fl;
    q[1] = 1; // root
    while (h < t) {
        sta = q[h++];
        for (int i = 0; i < 26; i++) {
            ch = tr[sta].son[i];
            if (sta == 1) fl = 1;
            else fl = tr[tr[sta].f].son[i];
            if (!ch) tr[sta].son[i] = fl;
            else {
                tr[ch].f = fl;
                tr[ch].fg |= tr[fl].fg;
                q[t++] = ch;
            }
        }
    }
}

void match() {
    int now = 1;
    int len = strlen(a);
    for (int i = 0, x, ch; i < len; i++) {
        x = a[i] - 'a';
        now = tr[now].son[x];
        if (tr[now].fg) {
            int up = now;
            while (tr[up].fg) {
                ans += tr[up].ct;
                tr[up].ct = 0;// 重复出现算一次
                up = tr[up].f;
            }
        }
    }
}

void clear() {
    for (int i = 0; i <= cnt; i++) {
        for (int j = 0; j < 26; j++)
            tr[i].son[j] = 0;
        tr[i].ct = tr[i].f = 0;
        tr[i].fg = false;
    }
    ans = 0;
}

int main() {
    scanf("%d", &cas);
    while (cas--) {
        cnt = 1;
        scanf("%d", &n);
        char str[55];
        for (int i = 0; i < n; i++) {
            scanf("%s", str);
            insert(str);
        }
        build_trie();
        scanf("%s", a);
        match();
        printf("%d\n", ans);
        clear();
    }
    return 0;
}

Trie树上的DP

待补充…