字符串统计

835. Trie字符串统计

Trie模版题

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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int son[N][26], cnt[N], idx;
void Insert(string s)
{
    int p = 0;
    for(int i = 0;s[i]; i++)
    {
        int u = s[i] - 'a';
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}
int Query(string s)
{
    int p = 0;
    for(int i = 0; s[i]; i++)
    {
        int u = s[i] - 'a';
        if(son[p][u]) p = son[p][u];
        else return 0;
    }
    return cnt[p];
}
int main()
{
    int n;  cin >> n;
    while(n--)
    {
        char op; cin >> op;
        string s; cin >> s;
        if(op == 'I')
        {
            Insert(s);
        }
        else
        {
            cout << Query(s) << '\n';
        }
    }
    return 0;
}

最大异或对

AcWing 143. 最大异或对

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
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 31 * N;
int son[M][2], idx;
int a[N];
void Insert(int a)
{
    int p = 0;
    for(int i = 30; i >= 0; i--)
    {
        int u = a >> i & 1;
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
}
int search(int a)
{
    int p = 0, res = 0;
    for(int i = 30; i >= 0; i--)
    {
        int u = a >> i & 1;
        if(son[p][!u])
        {
            p = son[p][!u];
            res = res * 2 + 1;
        }
        else
        {
            p = son[p][u];
            res = res * 2 + 0;
        }
    }
    return res;
}
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        Insert(a[i]);
    }
    int res = 0;
    for(int i = 0; i < n; i++)
        res = max(res, search(a[i]));
    cout << res;
    return 0;
}

KMP

831. KMP字符串

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
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
int n, m;
char p[N], s[M];
int ne[N];
int main()
{
    cin >> n >> p + 1 >> m >> s + 1;
    for(int i = 0, j = 2; j <= n; j++)//计算next数组
    {
        while(i && p[i + 1] != p[j]) i = ne[i];
        if(p[i + 1] == p[j]) i++;
        ne[j] = i;
    }
    for(int i = 0, j = 1; j <= m; j++)
    {
        while(i && p[i + 1] != s[j]) i = ne[i];
        if(p[i + 1] == s[j]) i++;
        if(i == n)
        {
            cout << j - n << " ";
            i = ne[i];
        }
    }
    return 0;
}

AC自动机

KMP：以\(O(n)\)判断一个单词在文章中出现的次数和具体的位置

Trie：计算一个单词出现的次数

AC自动机：以\(O(n)\)判断多个单词是否在文章中出现

搜索关键词

1282. 搜索关键词

计算一篇文章中出现了多少个列举的单词

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10, M = 1e6 + 10, S = 55;
int n;
int tr[N * S][26], cnt[N * S], idx;
char str[M];
int q[N * S], ne[N * S];
void insert()//创建trie树
{
    int p = 0;
    for(int i = 0; str[i]; i++)
    {
        int t = str[i] - 'a';
        if(!tr[p][t]) tr[p][t] = ++idx;
        p = tr[p][t];
    }
    cnt[p]++;
}
void build()
{
    int hh = 0, tt = -1;
    for(int i = 0; i < 26; i++)//因为根节点以及第一层的节点都是直接指向根节点，所以直接从第一层进行遍历即可
    {
        if(tr[0][i]) q[++tt] = tr[0][i];
    }
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = 0; i < 26; i++)
        {
            int p = tr[t][i];
            if(!p)//如果没有找到儿子节点，那么父节点对应的next指针就是要跳到的位置
                tr[t][i] = tr[ne[t]][i];
            else //如果存在儿子节点，那么这个节点的父亲节点的next指针对应的儿子节点字母i就是该儿子的next指针指向的位置
            {
                ne[p] = tr[ne[t]][i];
                q[++tt] = p;
            }
        }
        
    }
}
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(ne, 0, sizeof ne);
        idx = 0;
        cin >> n;
        for(int i = 0; i < n; i++)
        {
            cin >> str;
            insert();
        }
        build();
        cin >> str;//文章
        int res = 0;
        for(int i = 0, j = 0; str[i]; i++)
        {
            int t = str[i] - 'a';
            j = tr[j][t];
            int p = j;
            while(p)//因为如果p出现了，那么以p为前缀的单词一定也出现了，所以要不断更新为next指针
            //遍历到she的后缀he的时候 her的相同前缀he肯定是逐层遍历到了的 len(he)<len(she) 逐层遍历
            //把所有ne 指针全部加一遍  比如当前p到了she的e  把cnt[p]+进res后 
            //把p通过ne[p]跳到he的e 再加上此时指向he中e的p的cnt[p] 
            {
                res += cnt[p];
                cnt[p] = 0;//因为只记录是否出现过不记录个数，所以置为0
                p= ne[p];
            }
        }
        cout << res <<'\n';
    }
    return 0;
}