hdu-1075-What Are You Talking About-(사전 트리)

사전 트리 안에 각종 변수를 표시할 수 있다.
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
struct list
{
    int leap;
    char str[100];
    struct list *next[26];
};
struct list *tree;
struct list *code()
{
    int i;
    struct list *p;
    p=new list();
    p->leap=0;
    for(i=0;i<26;i++)
    {
        p->next[i]=NULL;
    }
    return p;
}
void in(struct list *q,char *str1,char *str2)
{
    int n,i,t;
    struct list *p;
    p=q;
    n=strlen(str2);
    for(i=0;i<n;i++)
    {
        t=str2[i]-'a';
        if(p->next[t]==NULL)
            p->next[t]=code();
        p=p->next[t];
    }
    p->leap=1;
    strcpy(p->str,str1);
}
void search(struct list *q,char *str)
{
    int n,i,t;
    n=strlen(str);
    struct list *p;
    p=q;
    for(i=0;i<n;i++)
    {
        t=str[i]-'a';
        if(p->next[t]==NULL)break;
        p=p->next[t];
    }
    if(p->leap==1&&i==n)
    printf("%s",p->str);
    else
    printf("%s",str);
}
int main()
{
    int i,j,n;
    char str1[100];
    char str2[100];
    char str[10000];
    tree=code();
    while(gets(str1)&&strcmp(str1,"START")!=0);
    while(scanf("%s",str1)&&strcmp(str1,"END")!=0)
    {
        scanf("%s",str2);
        in(tree,str1,str2);
    }
    while(gets(str)&&strcmp(str,"START")!=0);
    while(gets(str)&&strcmp(str,"END")!=0)
    {
        n=strlen(str);
        j=0;
        for(i=0;i<n;i++)
        {
            if(!(str[i]>='a'&&str[i]<='z'))
            {
                str1[j]='\0';
                search(tree,str1);
                printf("%c",str[i]);
                j=0;continue;
            }
            str1[j]=str[i];
            j++;
        }
        if(j!=0)
        {
            str1[j]='\0';
            search(tree,str1);
        }
        printf("
"); } return 0; }

좋은 웹페이지 즐겨찾기