首页 > 其他 > 详细

Luogu P2580 于是他错误的点名开始了 (Trie树模板)

时间:2019-08-05 14:36:22      阅读:75      评论:0      收藏:0      [点我收藏+]

传送

Trie树就是字典树,前缀树...(无所谓啦

今天考试的时候想出来了trie树怎么写,的确是正解,然而那题爆零了(...)

还是找个trie树板子写一下吧

*别忘了函数里字符串前的那个“*”

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn = 1e6+10;

int n,m,num;

struct node{
    int son[26];
    int cnt;
    bool fin;
}trie[maxn];

void insert(char *s){
    int u = 0;
    int len = strlen(s);
    for(int i = 0;i < len;i++){
        int v = s[i]-a;    
        if(!trie[u].son[v]) trie[u].son[v] = ++num;
        u = trie[u].son[v];
    }
    trie[u].fin = true;
}

int query(char *s){
    int u = 0;
    int len = strlen(s);
    for(int i = 0;i < len;i++){
        int v = s[i]-a;
        if(!trie[u].son[v]) return 2;
        u = trie[u].son[v];
    } 
    if(!trie[u].fin) return 2;
    if(!trie[u].cnt) {
        trie[u].cnt++;
        return 1;
    }
    return 3;
}
    
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
        char name[60] ;
        scanf("%s",name);
        insert(name);
    }
    scanf("%d",&m);
    for(int i = 1;i <= m;i++){
        char name[60] ;
        scanf("%s",name);
        int flag = query(name);
        if(flag == 1) printf("OK\n");
        if(flag == 2) printf("WRONG\n");
        if(flag == 3) printf("REPEAT\n");
    }
    return 0;
}

 

Luogu P2580 于是他错误的点名开始了 (Trie树模板)

原文:https://www.cnblogs.com/mogeko/p/11302744.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!