且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

hdu 1075 What Are You Talking About 字典树

更新时间:2021-10-26 00:25:45

  很简单的字典树,结果因为数组开小了,WA了近20次

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
struct node
{
    node *p[27];
    int v;
};
int m=0;
char s[500001][15];//开成300000就会一直WA
node *trie;
int ind;
void build(char *s,int nind)//生成树
{
    int i,len=strlen(s);
    node *now=trie,*next;
    for(i=0;i<len;i++)
    {
        next=now->p[s[i]-'a'];
        if(next==NULL)
        {
            next=(node *)malloc(sizeof(node));;
            memset(next,0,sizeof(node));
            next->v=-1;
        }
        now->p[s[i]-'a']=next;
        now=next;
    }
    now->v=nind;
}
void find(char *ss)//查找树
{
    int i;
    node *now=trie,*next;
    int last=-1,l=0;
    for(i=0;!i||ss[i-1];i++)
    {
        if(ss[i]<'a'||ss[i]>'z')//是不是单词结尾
        {
            if(ss[i]=='\0')ss[i]='\n';
            if(last!=-1)//有匹配单词
            {
                printf("%s%c",s[last],ss[i]);
                last=-1;
            }
            else//无匹配单词
            {
                for(;l<=i;l++)putchar(ss[l]);
            }
            if(ss[i]=='\n')ss[i]='\0';
            now=trie;
            l=i+1;

        }
        else
        {
            next=now?now->p[ss[i]-'a']:0;//判断now是不是空指针
            if(next==NULL)
            {
                for(;l<=i;l++)putchar(ss[l]);
                now=NULL;
                l=i+1;
                last=-1;
            }
            else
            {
                now=next;
                last=now->v;
            }
        }
    }
}
char a[3005],b[3005];
int main()
{
    trie=(node *)malloc(sizeof(node));
    memset(trie,0,sizeof(node));
    scanf("%*s");
    m=0;
    ind=1;
    while(~scanf("%s",s[m])&&strcmp(s[m],"END"))
    {
        scanf("%s",a);
        build(a,m);
        m++;
    }
    scanf("%*s");
    getchar();
    while(gets(a)&&strcmp(a,"END"))
    {
       find(a);
    }
}