当前位置:编程学习 > C/C++ >>

hdu 1075 What Are You Talking About (字典树)

题目大意:   类似解密过程,右边是单词对应的密文
                  给出一串字符,可以解密的单词都翻译出来
解题思路:   将明文存进数组,然后将密文建成Trie树
                  将最后结点存进树时顺便记录它明文的下标
                  搜索密文的每一个单词,若在树中则翻译出来
代码:
 
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#define MAX 100000  
struct snode{  
    int next[27];    //第一种写法  
    int w;  
}Tree[MAX*10];  
char ch1[MAX*11][11],ch2[11];  
int Index;  
void Insert(int k,int Tlen)     //遍历插入字典树  
{  
    int i,S=0,child;  
    for(i=1;i<=Tlen;i++)  
    {  
        child=ch2[i-1]-'a'+1;  
        if(Tree[S].next[child]==0)  
        {  
            if(i==Tlen)  
                Tree[Index].w=k;  
            Tree[S].next[child]=Index++;  
        }  
        else  
        {  
            if(i==Tlen)  
                Tree[Tree[S].next[child]].w=k;  
        }  
        S=Tree[S].next[child];  
    }  
}  
  
int Query(char ch5[],int Tlen)   //遍历查询字典树  
{  
    int i,S=0,child;  
    for(i=1;i<=Tlen;i++)  
    {  
        child=ch5[i-1]-'a'+1;  
        if(Tree[S].next[child]!=0)  
        {  
            if(i==Tlen&&Tree[Tree[S].next[child]].w!=0)  
            {  
                printf("%s",ch1[Tree[Tree[S].next[child]].w]);  
                 return 1;  
            }  
            S=Tree[S].next[child];  
        }  
        else  
            return 0;  
    }  
    return 0;  
}  
  
int main()  
{  
    int n=1,i,j;  
    char ch3[10000],ch4[20];  
    Index=1;  
    memset(Tree,0,sizeof(Tree));  
    scanf("%s",ch3);  
    while(scanf("%s",ch1[n]))  
    {  
        if(strcmp(ch1[n],"END")==0)  
            break;  
        scanf("%s",ch2);  
        Insert(n,strlen(ch2));  
        n++;  
    }  
    scanf("%s",ch3);  
    getchar();  
    while(gets(ch3))  
    {  
        if(strcmp(ch3,"END")==0)  
        {  
            break;  
        }  
        for(i=0,j=0;ch3[i]!='\0';i++)  
        {  
            if(ch3[i]<'a'||ch3[i]>'z')  //枚举每个单词是否存在翻译  
            {  
                if(Query(ch4,j)==0)  
                {  
                    printf("%s",ch4);  
                }  
                printf("%c",ch3[i]);  
                ch4[0]='\0';           //不存在初始化继续枚举下一个  
                j=0;  
            }  
            else  
            {  
                ch4[j++]=ch3[i];  
                ch4[j]='\0';  
            }  
        }  
        if(ch4[0]!='\0')               //***最后一个单词  
        {  
            if(Query(ch4,j)==0)  
                printf("%s",ch4);  
        }  
        puts("");  
    }  
    return 0;  
}  

 

 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,