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

· · 题解

一份简单易懂的题解

这是一道模板题，就不用多在前面BB什么废话了

_详细的解释会在代码中贴出来_

下面代码+分析

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
    int a[27];
    int kuan,log;
}e[5000000];//字典树e[t].a[],log,kuan分别表示当前节点t的a[]分支，是否访问过,当前(到a[])的单词个数

/* 例如 输入 abd则

e[0].a[0]=1,表示第一个单词abd的a表为1 然后e[1].a[1]=2,e[1].kuan=1,e[2].a[3]=3,e[2].kuan=1,e[3].kuan=1

有一个单词经过了1号2号3号节点，这里就有单词了

*/

char str[55];
int ta=0;//节点编号 
int n,m;
void build()//建字典树 
{
    int t=0;//虚拟节点编号 也就是第一个点 但它没有实际的单词意义 
    for(int i=0;i<strlen(str);i++)
    {
        if(!e[t].a[str[i]-'a']) //判断当前这个点的str[i]这个字母是否出现过 
        e[t].a[str[i]-'a']=++ta;//第一次出现-->添加节点ta 
        t=e[t].a[str[i]-'a'];//往下走 
        e[t].kuan++;//当前点的单词个数++ 
    }
}
int ask()//查询 
{
    int t=0;
    for(int i=0;i<strlen(str);i++)
    {
        if(!e[t].a[str[i]-'a']) return 0;//若根本没有这个单词经过，当前点的下一位没这个，就叫错了 
        t=e[t].a[str[i]-'a'];//否则往下走 
    }
    if(e[t].log) return 1;//访问过了 重复 
    e[t].log=1;//否则现在第一次访问标记 
    return 2;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",str);
        build();
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",str);
        int x=ask();
        if(x==0) printf("WRONG\n");
        else if(x==1) printf("REPEAT\n");
        else printf("OK\n");
    }
    return 0;
}

希望能帮到你

若有什么不对敬请指教[email protected]