【trie树】HDU1247Hat’s Words

Hat’s Words Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 19500 Accepted Submission(s): 6867Problem 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 wordSample Output ahat hatwordAuthor 戴帽子的Recommend Ignatius.L | We have carefully selected several similar problems for you: 1075 1671 1298 1800 2846 T

这道题也是比较简单的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

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的【trie树】HDU1247Hat’s Words的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。