henrytb 的博客

henrytb 的博客

题解 P2580 【于是他错误的点名开始了】

posted on 2019-04-15 18:16:24 | under 题解 |

裸的Trie

看到henry_y巨佬的题解发现有那么一点小问题

hack数据:

1
ab
1
a

正解输出WRONG,而TA的输出了OK

要注意Trie需要在每一个字符串末尾打一个结束标记(就是我这里的word数组)

否则点名点到的是名字的前缀也会被判对

其他没什么可说的,就是Trie的加入和查找

Code:

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int tot,Trie[500005][30],n,m,used[500005],word[500005];
char s[55];
void add(char *str){
    int len=strlen(str+1);
    int now=1;
    rep(k,1,len){
        int num=str[k]-'a';
        if(Trie[now][num])now=Trie[now][num];
        else Trie[now][num]=++tot,now=tot;
    }
    word[now]=1;
}
void search(char *str){
    int len=strlen(str+1);
    int now=1;
    rep(k,1,len){
        int num=str[k]-'a';
        if(Trie[now][num])now=Trie[now][num];
        else{
            printf("WRONG\n");
            return;
        }
    }
    if(!word[now])printf("WRONG\n");
    else if(!used[now])printf("OK\n"),used[now]=1;
    else printf("REPEAT\n");
}
int main(){
    scanf("%d",&n);
    rep(i,1,n) scanf("%s",s+1),add(s);
    scanf("%d",&m);
    rep(i,1,m) scanf("%s",s+1),search(s);
    return 0;
}