P2580于是他错误的点名开始了 trie树

bokaro_kyoku_mania · 2025-06-24 18:38:11 · 题解

trie字典树博客

P2580题目

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
char s[10101010];
int m;
int ch[1010101][26];
int idx;
int cnt[101011111];
void insert(char s[]){
    int p=0;
    for(int i=0;s[i];i++){
        int x=s[i]-'a';
        if(!ch[p][x])ch[p][x]=++idx;
        p=ch[p][x];
    }
    cnt[p]++;
}
int query(char s[]){
    int p=0;
    for(int i=0;s[i];i++){
        int x=s[i]-'a';
        if(!ch[p][x])return 0;
        p=ch[p][x];
    }
    if(cnt[p]>0){
        int anss=cnt[p];
        cnt[p]=-1;
        return anss;
    }
    return cnt[p];
}
signed main(){
//  ios::sync_with_stdio(0);
//  cin.tie(0),cout.tie(0);
    cin>>n;
    while(n--){
        scanf("%s",s);
        insert(s);
    }
    cin>>m;
    while(m--){
        scanf("%s",s);
        int op=query(s);
        if(op>0){
            printf("OK\n");
        }
        else if(op==-1){
            printf("REPEAT\n");
        }
        else if(op==0){
            printf("WRONG\n");
        }
    }

    return 0;
}

insert函数用来将班上人名插入树中。

query函数用来查询点到的人名。

如果第一次点到了办理存在的人，就把cnt[p]标记为-1，这样第二次重复点到就返回-1，直接输出REPEAT。

注意要将数组开大，不然会RE。