poj-2503+字典树入门题

poj--2503+字典树入门题

字典树入门题

将字符串结尾的标记为一个字符串，然后就可以用字典树的插入和查找了

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

#define maxn 26
typedef struct
{
    char str[13];
    int next[maxn];
}N;
N node[300001];
int top;

void insert(char *str,char *str1)
{
    int len=strlen(str);
    int t=0;
    for(int i=0;i<len;i++)
    {
        if(node[t].next[str[i]-'a']==0)
           node[t].next[str[i]-'a']=++top;
        t=node[t].next[str[i]-'a'];
    }
    strcpy(node[t].str,str1);
}

int search(char *str)
{
    int len=strlen(str);
    int t=0;
    for(int i=0;i<len;i++)
    {
        if(node[t].next[str[i]-'a']==0)
            return 0;
        t=node[t].next[str[i]-'a'];
    }
    printf("%s\n",node[t].str);
    return 1;
}

int main()
{
    char str1[20],str2[20],str[100];
    while(gets(str))
    {
        if(strlen(str)==0)
            break;
        sscanf(str,"%s %s",str1,str2);
        insert(str2,str1);
    }
    while(gets(str))
    {
        if(search(str)==0)
           printf("eh\n");
    }
  return 0;
}