Loading...

字典树 洛谷P2580

check评论:0 条 remove_red_eye浏览量:428 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-05-26

qwq,字典树就是一个非常可爱的可以查找单词的树qwq
实现原理这里不多说了qwq
code:

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int child[26];
    int visit;
    bool isword;
    node()
    {
        memset(child,0,sizeof(child));
        visit=0;
        isword=0;
    }
}nd[800000];
char s[60];
int n,m;
int h=0;
void ins()
{
    int l=strlen(s);
    int p=0;
    for(int i=0;i<l;i++)
    {
        int ch=s[i]-'a';
        if(!nd[p].child[ch])
        {
            h++;
            nd[p].child[ch]=h;
        }
        p=nd[p].child[ch];
        if(i==l-1)
        {
            nd[p].isword=1;
        }
    }
    return ;
}
void find()
{
    int l=strlen(s);
    int p=0;
    for(int i=0;i<l;i++)
    {
        int ch=s[i]-'a';
        if(!nd[p].child[ch])
        {
            printf("WRONG\n");
            return ;
        }
        p=nd[p].child[ch];
        if(i==l-1)
        {
            if(nd[p].isword==0)
            {
                printf("WRONG\n");
                return ;
            }
            if(nd[p].visit==0)
            {
                printf("OK\n");
                nd[p].visit=1;
                return ;
            } 
            else
            {
                printf("REPEAT\n");
                return ;
            }
        } 
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s);
        ins();
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        scanf("%s",s);
        find();
    } 
}

chevron_left HNOI2004 L语言
A+B Problem 题解 qwq chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名