鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > c++ > >

Trie树与AC自动机(未完成)

来源:互联网 作者:佚名 时间:2018-01-25 11:30
Trie树与AC自动机 作为现阶段的学习中个人应有的常识,AC自动机形象的来讲就是在Trie树上跑的一个KMP。由此,我们就先来谈一谈Trie树。(有图) 1. Trie树 又称单词查找树,字典树,一般用于字符串的匹配。它利用公共的字符串前缀进行查询,减少了无谓的操作,

Trie树与AC自动机


作为现阶段的学习中个人应有的常识,AC自动机形象的来讲就是在Trie树上跑的一个KMP。由此,我们就先来谈一谈Trie树。(有图)

1. Trie树

又称单词查找树,字典树,一般用于字符串的匹配。它利用公共的字符串前缀进行查询,减少了无谓的操作,是空间换时间的经典算法。举例:

pic

此图包含了{"to", "tea", "ted", "ten", "a", "i", "in", "inn"}这些字符串。

Trie树的基本性质可以归纳为:

  1. 根节点不包含字符,除根节点意外每个节点只包含一个字符。
  2. 从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符串不相同。

Trie树有两个基本操作,一为插入,二为删除,且两者复杂度均为\(O(len)\)(其中$len = $ 字符串长度)。

我们以对五个串aaaa,abb,aabbb,baa,bab的操作进行说明。

1.基本操作

1.插入

1. 插入aaaa

首先插入串aaaa。对树中没有的节点进行新建,连接。结果:

example1

对,就是这样的简单插入。(图中红色字母代表一个单词的结尾)

2. 插入abb

再插入串abb。在插入时,已有的节点直接走过去,没有的就插入再走过去。结果:

1.插入a

example2

2.插入b

example3

3.再插入b

example4

完成。

3.插入aabbb

不再赘述,此操作请认真思考。结果:

example5

4.插入baa

因为根节点的儿子中没有b,所以我们要在根节点后挂上一个b。其余的新建与第一个串一样。结果:

example5

5.插入bab

与第二个串相同。结果:

example6

结束。

2.查询

为了避免冗余,我们用简单的几张图片表示过程。以串aabbb为例:

example7

example8

example9

example9

example10

完成。

简单的操作就是这些。但在实际应用中,往往不只是单纯返回一个串,更常用的是返回此处是否有串,或是串的个数,抑或状态。下面我们以几个题目做例子。

2.题目

1.洛谷P2580 于是他错误的点名开始了

大意:

给定\(n\)个字典串,再对\(m\)个模式串进行匹配,若匹配到,输出\(O\),未匹配到,输出\(WRONG\),若匹配到且之前已经被匹配,输出\(REPEAT\)

解:真的是很基本的Trie树的题,此题在这里是做代码范例用途。详细解释见代码。(不要在意这神奇的代码风格)

#include <iostream>
#define re register
const int MAXN = 1000001;
struct Trie{                //定义Trie树的结构,因为当前节点后可能会有26个小写字母,也就是26个后继,所以数组开26大小。
    int next[26];
    bool exist, repeat;     //exist:是否是字符串结尾(当前位置是否有字符串);repeat:此字符串是否被查询过。
}a[MAXN];
int top, n, m;
std::string str;
inline void Trie_insert() {
    int iter(0), now(0), tmp(0);        //iter:指向字符;now:指向节点。此两者起指针作用。
    for (iter; str[iter]; ++iter) {     //遍历当前插入字符串。
        tmp = str[iter] - 'a';          //将当前字母用数字表示。
        if(!a[now].next[tmp]) a[now].next[tmp] = ++top;     //如果当前节点没有代表该字母的后继,则新建节点。
        now = a[now].next[tmp];         //将指针向后移。
    }
    a[now].exist = true;                //当前节点代表字符串结尾。
    return ;
}
inline int Trie_search() {
    int iter(0), now(0), tmp(0);
    for (iter; str[iter]; ++iter) {     //遍历当前查询字符串。
        tmp = str[iter] - 'a';          //与上方操作相同。
        if(!a[now].next[tmp]) return 0; //如果当前节点没有代表该字母的后继,则说明查询失败,返回零。
        now = a[now].next[tmp];         //指针后移。
    }
    return a[now].exist ? (!a[now].repeat ? (a[now].repeat = 1) : 2) : 0;
  /*
        相当于:
        if(a[now].exist) {              //判断是否存在
            if(a[now].repeat) return 2; //判断是否查询过
            else {a[now].repeat = 1; return 1;}
        }
        else return 0;
  */
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin >> n;
    for (re int i = 1; i <= n; ++i) std::cin >> str, Trie_insert();
    std::cin >> m;
    for (re int i = 1; i <= m; ++i) {
        std::cin >> str;
        switch(Trie_search()) {     //得到查询的返回值。若是0,说明匹配未成功;是1,说明匹配成功;是2,说明匹配成功,且重复匹配。
            case (0): {
                std::cout << "WRONG\n";
                break;
            }
            case (1): {
                std::cout << "OK\n";
                break;
            }
            default: {
                std::cout << "REPEAT\n";
            }
        }
    }
    return 0;
}

就是这样。

2.洛谷P2922 [USACO08DEC] 秘密消息Secret Message

大意:

给定\(M(1 \leqslant M \leqslant 50000)\)个字典串,第\(i\)个字典串有\(Bi(1 \leqslant Bi \leqslant 10000)\)位。再给定N(\(1 \leqslant N \leqslant 50000\))个模式串,第\(i\)个模式串有\(Cj\)(\(1 \leqslant Cj \leqslant 10000\))位 (\((\sum_{i = 1}^{M}Bi + \sum_{j = 1}^{N}Cj) \leqslant 500000\))。对每个模式串\(j\),求有多少串与当前模式串有相同前缀。(包括长度长于,等于与小于模式串的字典串)

解:在插入沿途做经过的标记,标记当前字母被几个字符串经过。在查询时\(ans\)加上经过字母上的结束标记。查询结束时,如果是走到字典串结尾而结束,\(ans\)加上结束标记,直接退出;如果是走到模式串结尾而结束,\(ans\)则不加结束标记,而是要加上经过标记,然后退出。

前面的加结束标记好理解,但为什么字典串比模式串长时要加经过标记呢?因为字典串比模式串长,说明字典串以模式串为前缀,按题意求有多少串与当前模式串有相同前缀,又因为经过标记正好代表这些串的个数,当然要用经过标记了。

这一道题思维量并不大,也算一道入门题。

#include <cctype>
#include <cstdio>
const int N = 10000;
struct Node{
    int next[2], exist, passby;         //exist:结束标记;passby:经过标记。
}cow[500010];
int m, n, b, j, tot, top;
bool fl(0);
char buf[N], *p = buf, *end = buf;
inline char Get_char() {
    if(p == end) {
        if(feof(stdin)) return (0);
        p = buf; end = buf + fread(buf, 1, N, stdin);
    }
    return *(p++);
}
inline void Get_int(int &x) {
    x = 0; char c(0);
    while (!isdigit(c = Get_char()));
    do {x = (x << 1) + (x << 3) + (c ^ 48);}
    while (isdigit(c = Get_char()));
    return ;
}
inline void Insert(int lent) {
    int now(0), c(0);
    for (int i = 1; i <= lent; ++i) {
        Get_int(c);
        if(!cow[now].next[c]) cow[now].next[c] = ++top;
        cow[cow[now].next[c]].passby++;         //普通插入,只不过多了经过标记。
        now = cow[now].next[c];
    }
    cow[now].exist++;
    return ;
}
inline void Query(int lent) {
    int now(0), c(0); tot = 0; fl = false; int i;
    for (i = 1; i <= lent; ++i) {
        Get_int(c);
        if(!cow[now].next[c]) {fl = true; break;}   //标记第一种情况,即字典串比模式串短。
        now = cow[now].next[c];
        tot += cow[now].exist;                      //加结束标记。
    }
    for (i = i + 1; i <= lent; ++i)
        Get_int(c);
    if(fl) {printf("%d\n", tot);}
    else {printf("%d\n", tot - cow[now].exist + cow[now].passby);}  //第二种情况,即字典串比模式串长,则减掉之前加上的结束标记,加上经过标记。
    return ;
}
int main() {
    Get_int(m); Get_int(n);             //不要在意快读。
    for (int i = 1; i <= m; ++i) {
        Get_int(b); Insert(b);          //插入操作。
    }
    for (int i = 1; i <= n; ++i) {
        Get_int(j); Query(j);           //查询操作。
    }
    return 0;
}

3.待添加

2.AC自动机

网友评论
<