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

 

题目背景

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。

题目背景太真实了，XS中学 × 山东省实验中学√

模板题。在search函数里统计当前节点作为查询末尾出现了几次即可。

#include <bits/stdc++.h>
using namespace std;
int trie[1000005][26],tot=1;
int eend[1000005]={0},cnt[1000005]={0};
void insert(string s)
{
    int len=s.size();
    int k,p=1;
    for(k=0;k<len;k++)
    {
        int ch=s[k]-'a';
        if(trie[p][ch]==0) trie[p][ch]=++tot;
        p=trie[p][ch];
    }
    eend[p]=1;
}
int search(string s)
{
    int len=s.size(),k,p=1; 
    for(k=0;k<len;k++)
    {
        p=trie[p][s[k]-'a'];
        if(p==0) return 0;
    }
    if(eend[p])
    {
        cnt[p]++;
        return cnt[p];
    }
    else
    {
        return 0;
    }
}
int main()
{
    int n,m;
    cin>>n;
    int i;
    for(i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        insert(s);
    } 
    cin>>m;
    for(i=1;i<=m;i++)
    {
        string s;
        cin>>s;
        int temp=search(s);
        if(temp==0) cout<<"WRONG"<<endl;
        else if(temp==1) cout<<"OK"<<endl;
        else cout<<"REPEAT"<<endl;
    }
    return 0;
}