Trie 树

Trie树挺简单的就不介绍了，放一下代码。

一下四种写法的代码都以P2580 于是他错误的点名开始了这道经典题作为模板，记录了一些评测信息。

使用指针的递归版本

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
#include<bits/stdc++.h>
// Recursive version using pointers
// Using C++14(GCC9)
// 576ms/63.32MB without O2
// 478ms/63.35MB with O2
namespace Pozhu{
using namespace std;
#define N 10010
#define M 100010

struct Trie
{
    Trie* son[26];
    char val;
    int cnt;
    bool iskey;
    int be_find;
    Trie() : 
    val(0),cnt(0),iskey(false),be_find(false)
    {for(int i = 0;i < 26;i++) son[i] = nullptr;}
    Trie(char _v) : 
    val(_v),cnt(1),iskey(false),be_find(false)
    {for(int i = 0;i < 26;i++) son[i] = nullptr;}
    int find(char* s,int len)
    {
        if(!len)
        {
            if(iskey) return ++be_find;
            else return 0;
        }
        if(son[s[0] - 'a'] == nullptr) return 0;
        return son[s[0] - 'a'] -> find(s+1,len-1);
    }
    int find(char* s)
    {
        return find(s,strlen(s));
    }

    void add(char* s,int len)
    {
        if(!len) return iskey = true,void();
        if(son[s[0] - 'a'] == nullptr) son[s[0] - 'a'] = new Trie(s[pos]);
        else son[s[0] - 'a'] -> cnt++;
        son[s[0] - 'a'] -> add(s+1,len-1);
    }
    void add(char* s)
    {
        add(s,strlen(s));
    }
}rt;
int n,m;
char s[60];

void main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%s",s);
        rt.add(s);
    }
    scanf("%d",&m);
    for(int i = 1;i <= m;i++)
    {
        scanf("%s",s);
        int x = rt.find(s);
        if(!x) puts("WRONG");
        else if(x == 1) puts("OK");
        else puts("REPEAT");
    }
    return;
}

}

signed main()
{
    Pozhu :: main();
    return 0;
}

使用指针的非递归版本

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
#include<bits/stdc++.h>
// Non-recursive version using pointers
// Using C++14(GCC9)
// 564ms/63.34MB without O2
// 449ms/63.29MB with O2
namespace Pozhu{
using namespace std;
#define N 10010
#define M 100010

struct Trie
{
    Trie* son[26];
    char val;
    int cnt;
    bool iskey;
    int be_find;
    Trie() : 
    val(0),cnt(0),iskey(false),be_find(false)
    {for(int i = 0;i < 26;i++) son[i] = nullptr;}
    Trie(char _v) : 
    val(_v),cnt(1),iskey(false),be_find(false)
    {for(int i = 0;i < 26;i++) son[i] = nullptr;}
}rt;

int find(char* s)
{
    int len = strlen(s),pos = 0;
    Trie* now = &rt;
    while(pos < len)
    {
        if(now -> son[s[pos] - 'a'] == nullptr) return 0;
        now = now -> son[s[pos] - 'a'];
        pos++;
    }
    if(now -> iskey) return ++now -> be_find;
    else return 0;
}

void add(char* s)
{
    int len = strlen(s),pos = 0;
    Trie* now = &rt;
    while(pos < len)
    {
        if(now -> son[s[pos] - 'a'] == nullptr) now -> son[s[pos] - 'a'] = new Trie(s[pos]);
        else now -> son[s[pos] - 'a'] -> cnt++;
        now = now -> son[s[pos] - 'a'];
        pos++;
    }
    return now -> iskey = true,void();
}

int n,m;
char s[60];

void main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%s",s);
        add(s);
    }
    scanf("%d",&m);
    for(int i = 1;i <= m;i++)
    {
        scanf("%s",s);
        int x = find(s);
        if(!x) puts("WRONG");
        else if(x == 1) puts("OK");
        else puts("REPEAT");
    }
    return;
}

}

signed main()
{
    Pozhu :: main();
    return 0;
}

使用数组的递归版本

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<bits/stdc++.h>
// Recursive version using arrays
// Using C++14(GCC9)
// 518ms/57.81MB without O2
// 466ms/57.79MB with O2
namespace Pozhu{
using namespace std;
#define N 10010
#define M 100010

int tot = 1;

struct Trie
{
    int son[26];
    char val;
    int cnt;
    bool iskey;
    int be_find;
    Trie() : 
    val(0),cnt(0),iskey(false),be_find(false){}
    Trie(char _v) : 
    val(_v),cnt(1),iskey(false),be_find(false)
    {memset(son,0,sizeof(son));}
    int find(char* s,int len);
    int find(char* s);
    void add(char* s,int len);
    void add(char* s);
}t[N * 50];

int Trie :: find(char* s,int len)
{
    if(!len)
    {
        if(iskey) return ++be_find;
        else return 0;
    }
    if(!son[s[0] - 'a']) return 0;
    return t[son[s[0] - 'a']].find(s+1,len-1);
}
int Trie :: find(char* s)
{
    return find(s,strlen(s));
}

void Trie :: add(char* s,int len)
{
    if(!len) return iskey = true,void();
    if(!son[s[0] - 'a']) son[s[0] - 'a'] = ++tot,t[tot] = Trie(s[pos]);
    else t[son[s[0] - 'a']].cnt++;
    t[son[s[0] - 'a']].add(s+1,len-1);
}
void Trie :: add(char* s)
{
    add(s,strlen(s));
}

int n,m;
char s[60];

void main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%s",s);
        t[1].add(s);
    }
    scanf("%d",&m);
    for(int i = 1;i <= m;i++)
    {
        scanf("%s",s);
        int x = t[1].find(s);
        if(!x) puts("WRONG");
        else if(x == 1) puts("OK");
        else puts("REPEAT");
    }
    return;
}

}

signed main()
{
    Pozhu :: main();
    return 0;
}

使用数组的非递归版本

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
#include<bits/stdc++.h>
// Non-recursive version using arrays
// Using C++14(GCC9)
// 476ms/57.81MB without O2
// 463ms/57.81MB with O2
namespace Pozhu{
using namespace std;
#define N 10010
#define M 100010

int tot = 1;

struct Trie
{
    int son[26];
    char val;
    int cnt;
    bool iskey;
    int be_find;
    Trie() : 
    val(0),cnt(0),iskey(false),be_find(false){}
    Trie(char _v) : 
    val(_v),cnt(1),iskey(false),be_find(false)
    {memset(son,0,sizeof(son));}
    int find(char* s,int len);
    int find(char* s);
    void add(char* s,int len);
    void add(char* s);
}t[N * 50];

int find(char* s)
{
    int len = strlen(s),pos = 0;
    int now = 1;
    while(pos < len)
    {
        if(!t[now].son[s[pos] - 'a']) return 0;
        now = t[now].son[s[pos] - 'a'];
        pos++;
    }
    if(t[now].iskey) return ++t[now].be_find;
    else return 0;
}

void add(char* s)
{
    int len = strlen(s),pos = 0;
    int now = 1;
    while(pos < len)
    {
        if(!t[now].son[s[pos] - 'a']) t[now].son[s[pos] - 'a'] = ++tot,t[tot] = Trie(s[pos]);
        else t[t[now].son[s[pos] - 'a']].cnt++;
        now = t[now].son[s[pos] - 'a'];
        pos++;
    }
    return t[now].iskey = true,void();
}

int n,m;
char s[60];

void main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%s",s);
        add(s);
    }
    scanf("%d",&m);
    for(int i = 1;i <= m;i++)
    {
        scanf("%s",s);
        int x = find(s);
        if(!x) puts("WRONG");
        else if(x == 1) puts("OK");
        else puts("REPEAT");
    }
    return;
}

}

signed main()
{
    Pozhu :: main();
    return 0;
}

大概就是这样，总结一下就是内存上数组实现比指针实现略占优势，O2条件下使用指针的非递归版本最快，不开O2时使用数组的非递归版本最快。

AC 自动机

放一下简单版的代码 ： 

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
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 1000010

struct node{
    int fail;
    int son[26];
    int end;
}t[N];
int tot,n;
char s[N];
#define son(x,i) (t[x].son[i])

void insert(char* s);
int query(char* s);
void getfail();

void main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%s",s);
        insert(s);
    }
    getfail();
    scanf("%s",s);
    printf("%d",query(s));
    return;
}

int query(char* s)
{
    int len = strlen(s);
    int nw = 0,ans = 0;
    for(int i = 0;i < len;i++)
    {
        nw = son(nw,s[i]-'a');
        for(int nt = nw;nt && ~t[nt].end;nt = t[nt].fail)
        {
            ans += t[nt].end;
            t[nt].end = -1;
        }
    }
    return ans;
}

void getfail()
{
    queue<int>q;
    for(int i = 0;i < 26;i++)
    {
        if(son(0,i))
        {
            t[son(0,i)].fail = 0;
            q.emplace(son(0,i));
        }
    }
    while(q.size())
    {
        int x = q.front();q.pop();
        for(int i = 0;i < 26;i++)
        {
            if(son(x,i)) t[son(x,i)].fail = son(t[x].fail,i),q.emplace(son(x,i));
            else son(x,i) = son(t[x].fail,i);
        }
    }
}

void insert(char* s)
{
    int len = strlen(s);
    int nw = 0;
    for(int i = 0;i < len;i++)
    {
        if(!son(nw,s[i]-'a')) son(nw,s[i]-'a') = ++tot;
        nw = son(nw,s[i]-'a');
    }
    t[nw].end++;
}

}

signed main()
{
    Pozhu :: main();
    return 0;
}