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

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

 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

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int seg[MAXN][26], cnt[MAXN * 26], idx;
void Insert(char *str) {
    int u = 0;
    for (int i = 0; str[i]; i++) {
        int v = str[i] - 'a';
        if (!seg[u][v])
            seg[u][v] = ++idx;
        u = seg[u][v];
    }
    cnt[u]++;
}
int Query(char *str) {
    int u = 0;
    for (int i = 0; str[i]; i++) {
        int v = str[i] - 'a';
        if (!seg[u][v])
            return 0;
        u = seg[u][v];
    }
    return cnt[u];
}
int main() {
    int n;
    char op, str[MAXN];
    scanf("%d", &n);
    while (n--) {
        scanf(" %c %s", &op, str);
        if (op != 'Q')
            Insert(str);
        else printf("%d\n", Query(str));
    }
    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

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int son[N][26], cnt[N], idx;
string s;
int n,m;
void insert(string str){
    int p =0;
    for(int i =0;i<str.size();i++){
        int u = str[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
}
int query(string str){
    int res=0;
    int p =0;
    for(int i =0;i<str.size();i++){
        int u = str[i]-'a';
        p=son[p][u];
        if (p == 0) return res;
        res += cnt[p];
    }
    return res;
}
int main()
{
    cin>>n>>m;
    while (n -- ){
        cin>>s;
        insert(s);
    }
    while (m -- ){
        cin>>s;
        int res = query(s);
        cout<<res<<endl;
    }
    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

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5,M=31*N;
int a[N];
int son[M][2],idx=0;
int n;
void insert(int t){
    int p = 0;
    for(int i =30;i>=0;i--){
        int u = t>>i&1;
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
}
int query(int t){
    int p = 0,res=0;
    for(int i =30;i>=0;i--){
        int u = t>>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()
{
    cin>>n;
    int res = 0;
    idx=0;
    for (int i = 0; i < n; i ++ ){
        cin>>a[i];
        insert(a[i]);
    }
    for (int i = 0; i < n; i ++ ){
        res=max(res,query(a[i]));
    }
    cout<<res<<endl;
    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

#include<bits/stdc++.h>
using namespace std;
int t,n;
const int N = 100000;
int son[N][10],idx,cnt[N];
string a[N];
bool flag;
void insert(string s){
    int p =0;
    for(int i=0;i<s.size();i++){
        int u = s[i]-'0';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
        if(cnt[p]) flag=false;
    }
    cnt[p]++;
    
}
int main()
{
    cin>>t;
    while(t--){
        cin>>n;
        for(int i =0;i<n;i++){
            cin>>a[i];
        }
        sort(a,a+n);
        flag = true;
        for(int i =0;i<n;i++){
            insert(a[i]);
        }
        if(flag){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
        idx=0;
        memset(cnt, 0, sizeof cnt);
        memset(son, 0, sizeof son);
    }
    
    return 0;
}