首页 > 其他 > 详细

luogu2580 于是他错误的点名开始了 Trie树

时间:2017-11-29 20:41:11      阅读:232      评论:0      收藏:0      [点我收藏+]

模板题

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
struct Node{
    int cnt, son[29];
    bool hav;
    Node(){
        cnt = hav = 0;
    }
}trie[500005];
int c, n, m, len;
char s[55];
void ins(){
    int u=0;
    for(int i=0; i<len; i++){
        int v=s[i]-‘a‘;
        if(!trie[u].son[v]) trie[u].son[v] = ++c;
        u = trie[u].son[v];
    }
    trie[u].hav = true;
}
int que(){
    int u=0;
    for(int i=0; i<len; i++){
        int v=s[i]-‘a‘;
        if(!trie[u].son[v]) return 3;
        u = trie[u].son[v];
    }
    if(!trie[u].hav)    return 3;
    if(!trie[u].cnt){
        trie[u].cnt++;
        return 1;
    }
    return 2;
}
int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        scanf("%s", s);
        len = strlen(s);
        ins();
    }
    cin>>m;
    for(int i=1; i<=m; i++){
        scanf("%s", s);
        len = strlen(s);
        int t=que();
        if(t==1)    printf("OK\n");
        else if(t==2)   printf("REPEAT\n");
        else    printf("WRONG\n");
    }
    return 0;
}

luogu2580 于是他错误的点名开始了 Trie树

原文:http://www.cnblogs.com/poorpool/p/7922496.html

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