【trie树】HDU1247Hat’s Words-蒲公英云

【trie树】HDU1247Hat’s Words

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

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 }