字典树 HDU 1075 What Are You Talking About

http://acm.hdu.edu.cn/showproblem.php?pid=1075

#include<iostream>
#include<algorithm>
#include<cstring>
#include<ctype.h>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

struct node
{
    int flag;
    char str[15];
    node *next[26];
   /* node()
    {
        memset(next, NULL, sizeof(next));
        flag=0;
    }*/
    node():flag(0){memset(next, NULL, sizeof(next));};
};
node *head=new node();

void connect(char *a, char *b)
{
    node *p=head;
    //node *p=new node();
    for(int i=0; a[i]; i++)
    {
        int k=a[i]-‘a‘;
        if(p->next[k]==NULL)
            p->next[k]=new node();
        p=p->next[k];
    }
    p->flag=1;
    strcpy(p->str, b);
}
char *query(char *s)
{
    node *p=head;
    for(int i=0; s[i]; i++)
    {
        int k=s[i]-‘a‘;
        if(p->next[k]==NULL)
            return NULL;
        p=p->next[k];
    }
    if(p->flag==1)
        return p->str;
    else
        return NULL;
}
int main()
{
    char m[15], e[15], b[3030], f[15];
    gets(m);
    while(scanf("%s", m), strcmp(m, "END")!=0)
    {
        scanf("%s", e);
        connect(e, m);
    }
    scanf("%s", b);
    getchar();
    while(gets(b), strcmp(b, "END")!=0)
    {
        int i, j;

        for(i=0; b[i]; i++)
        {
            j=0;
            while(b[i]>=‘a‘&&b[i]<=‘z‘)
            {
                f[j++]=b[i];
                i++;
            }
            f[j]=0;
            char *k=query(f);
            /*char k[15];
             k=query(f);*/
            if(k==0)
                printf("%s", f);
            else
                printf("%s", k);
            printf("%c", b[i]);
        }
        printf("\n");
    }
    return 0;
}

字典树 HDU 1075 What Are You Talking About

原文：http://www.cnblogs.com/wazqWAZQ1/p/4692933.html