【trie树】HDU1247Hat’s Words

迷南。 2022-01-09 05:41 291阅读 0赞

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

Hat’s Words
    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
    Total Submission(s): 19500    Accepted Submission(s): 6867
    
    
    Problem Description
    A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
    You are to find all the hat’s words in a dictionary.
    
     
    
    Input
    Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 50,000 words.
    Only one case.
    
     
    
    Output
    Your output should contain all the hat’s words, one per line, in alphabetical order.
     
    
    Sample Input
    a
    ahat
    hat
    hatword
    hziee
    word
     
    
    Sample Output
    ahat
    hatword
     
    
    Author
    戴帽子的
     
    
    Recommend
    Ignatius.L   |   We have carefully selected several similar problems for you:  1075 1671 1298 1800 2846

这道题也是比较简单的trie树的题，开始觉得很懵逼，最后才发现其实暴力就可以

对于每个单词枚举断点，然后查前后是否都存在

我们来计算下时间复杂度，假设n个单词，每个单词长度最大为m

那么插入O（nm）；

查询时候O（nmm）；

总复杂度O（nm+m2n）；

这道题的n是50000，m假设是30，那么很明显可以过

上代码

1 #include<cstdio>
     2 #include<algorithm>
     3 #include<cstring>
     4 #define idx(i) (i-'a')
     5 #define N 50011
     6 using namespace std;
     7 char in[N][300];
     8 int cnt=1,pp;
     9 struct TRIE{
        int nxt[30],cnt;}tree[N*300];
    10 inline int regist(){
        return cnt++;}
    11 void insert(char *now)
    12 {
    13     int c,rt=0,len=strlen(now);
    14     for(int i=0;i<len;i++)
    15     {
    16         c=idx(now[i]);
    17         if(!tree[rt].nxt[c])
    18             tree[rt].nxt[c]=regist();
    19         rt=tree[rt].nxt[c];
    20     }
    21     tree[rt].cnt=1;
    22 }
    23 bool find(char *now,int st,int ed)
    24 {
    25     int rt=0;
    26     for(int i=st-1;i<ed;i++)
    27     {
    28         if(!tree[rt].nxt[idx(now[i])])return 0;
    29         rt=tree[rt].nxt[idx(now[i])];
    30     }
    31     return tree[rt].cnt;
    32 }
    33 int main()
    34 {
    35     while(scanf("%s",in[++pp]+1)!=EOF)insert(in[pp]+1);
    36     for(int i=1;i<pp;i++)
    37     {
    38         int len=strlen(in[i]+1);
    39         for(int j=1;j<=len;j++)
    40             if(find(in[i]+1,1,j)&&find(in[i]+1,j+1,len)){printf("%s\n",in[i]+1);break;}
    41     }
    42     return 0;
    43 }

转载于:https://www.cnblogs.com/Qin-Wei-Kai/p/10224182.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/9479c39905bc48b5b318c11df8d1347d.png