What Are You Talking About HDU1075[通俗易懂]

全栈程序员-站长 • 2022年7月4日下午12:16 • 未分类 • 阅读 27

大家好，又见面了，我是你们的朋友全栈君。

一开始我也想用map 但是处理不好其他字符。。

看了题解多多学习！很巧妙就是粗暴的一个字符一个字符的来分为小写字母和非小写字母两个部分一但单词结束的时候就开始判断。

What Are You Talking About HDU1075[通俗易懂]

#include<bits/stdc++.h>
using namespace std;

int main()
{
    string a,b;
    map<string ,string >ma;
    cin>>a;
    while(cin>>a&&a!="END")
    {
        cin>>b;ma[b]=a;

    }
    cin>>a;
    char s[3500];getchar();
    while(gets(s))
    {
        if(!strcmp(s,"END"))break;

        int n=strlen(s);
        a="";
        for(int i=0;i<n;i++)
        {
         if(islower(s[i]))a+=s[i];
         else
         {
             if(ma.find(a)!=ma.end())
                cout<<ma[a];

             else
                 cout<<a;

             cout<<s[i];
             a="";


         }


        }
        cout<<endl;


    }




}

View Code

字典树写法

注意malloc 和初始化字符串赋值用strcpy 不申请内存根本无法使用

因为 gets 和getchar 的问题检查了半小时注意！！！

gets会吸收\n给忘记了。。。。

有关字典树的指针写法规范一下

#include <iostream>
#include <cstdio>
#include <cstring>
#include<malloc.h>
using namespace std;

struct node
{
    char *val;
    node *next[26];
    int flag;
    node()
    {
        for(int i=0;i<26;i++)
        {
            next[i]=NULL;

        }
        flag=0;
    }
};
node *p,*root=new node();

void change(char *s,char *v)
{
    p=root;
    for(int i=0;s[i]!='\0';i++)
    {
        int ch=s[i]-'a';
        if(p->next[ch]==NULL)
            p->next[ch]=new node();
        p=p->next[ch];

    }
    p->flag=1;
    p->val=(char*)malloc((strlen(v)+1)*sizeof(char));
    strcpy(p->val,v);

}

void find1(char *s)
{
    p=root;
    for(int i=0;s[i]!='\0';i++)
    {
        int ch=s[i]-'a';
        if(p->next[ch]==NULL)
        {
            printf("%s",s);return;
        }
        p=p->next[ch];
    }
   if(p->flag)printf("%s",p->val);
   else   printf("%s",s);

}

int main()
{
     char a[3010],b[3010];
     gets(a);
     while(scanf("%s",a)==1)
     {
         if(!strcmp(a,"END"))break;
         scanf("%s",b);
         change(b,a);

     }
    
     getchar();
     gets(a);
     char s[3010];
     while(gets(a))
     {
         if(!strcmp(a,"END"))break;
         int k=0;
         for(int i=0;i<strlen(a);i++)
         {
             if(islower(a[i]))s[k++]=a[i];
             else
             {
                 s[k]='\0';
                 find1(s);
                 printf("%c",a[i]);
                 k=0;
             }
         }

         printf("\n");
     }

return 0;
}