209
hdu 1075 What Are You Talking About 字典树
很简单的字典树，结果因为数组开小了，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);
}
}
最后更新：2017-04-03 18:51:45