【模版】trie树

洛谷P2580 于是他错误的点名开始了

题目背景

XS中学化学竞赛组教练是一个酷爱炉石的人。
他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次，然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉（详情请见已结束比赛CON900）。

题目描述

这之后校长任命你为特派探员，每天记录他的点名。校长会提供化学竞赛学生的人数和名单，而你需要告诉校长他有没有点错名。（为什么不直接不让他玩炉石。）

输入输出格式

• 输入格式：
  第一行一个整数 n，表示班上人数。接下来 n 行，每行一个字符串表示其名字（互不相同，且只含小写字母，长度不超过 50）。第 n+2 行一个整数 m，表示教练报的名字。接下来 m 行，每行一个字符串表示教练报的名字（只含小写字母，且长度不超过 50）。
• 输出格式：
  对于每个教练报的名字，输出一行。如果该名字正确且是第一次出现，输出“OK”，如果该名字错误，输出“WRONG”，如果该名字正确但不是第一次出现，输出“REPEAT”。（均不加引号）

输入输出样例

• 输入样例1：
  5
  a
  b
  c
  ad
  acd
  3
  a
  a
  e
• 输出样例1：
  OK
  REPEAT
  WRONG

说明

对于 40%的数据，n≤1000,m≤2000；
对于 70%的数据，n≤10000,m≤20000；
对于 100%的数据， n≤10000，m≤100000。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
//字符串最长长度50*字符串数目10000=500000
const int maxn=500005;

class Trie
{
public:
    Trie()
    {
        size=0;
        memset(ch,0,sizeof(ch));
        memset(vis,0,sizeof(vis));
    }
    void insert(char *s);
    void search(char *s);
    
private:
    int size;
    //a-z共26个字母以及标志符号‘$‘
    //ch[i][j]表示总体第i个插入第字母后面的字母j+'a'
    int ch[maxn][27];
    //用于标记这个串是否出现过
    bool vis[maxn];
    inline int trans(char c)
    {
        if(c=='$') return 26;
        return c-'a';
    }
    
}tree;

void Trie::insert(char *s)
{
    int u=0;
    int len=strlen(s);
    for(int i=0;i<len;i++)
    {
        int c=trans(s[i]);
        //如果以前没有插入过该字母，就插入新节点
        if(!ch[u][c]) ch[u][c]=++size;
        //然后不论怎样进入新的节点
        u=ch[u][c];
    }
}

void Trie::search(char *s)
{
    int u=0;
    int len=strlen(s);
    for(int i=0;i<len;i++)
    {
        int c=trans(s[i]);
        //如果该字符没有被插入过，说明此串没出现过
        if(!ch[u][c])
        {
            printf("WRONG\n");
            return;
        }
        //继续检查后续字母
        u=ch[u][c];
    }
    //检查到最后：如果没有被标记过说明第一次出现，并标记该字符
    if(!vis[u])
    {
        printf("OK\n");
        vis[u]=true;
        return;
    }
    printf("REPEAT\n");
}
//为了防止一些字符串是另一些的前缀，我们加工一下这个字符串：结尾增添'$'
void deal(char *str)
{
    scanf("%s",str);
    int len=strlen(str);
    str[len]='$';
    str[len+1]='\0';
}

int main()
{
//    freopen("in.in","r",stdin);
//    freopen("out.out","w",stdout);
    int n,m;
    char str[55];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        deal(str);
        tree.insert(str);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        deal(str);
        tree.search(str);
    }
    return 0;
}