Hat’s WordsTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 10889Accepted Submission(s): 3903
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
aahathathatwordhzieeword
Sample Output
ahathatword
题目大意：
给出一些字符串，输出其中的部分字符串,这些字符串可以拆分成其他字符串。解题思路：首先用map标记字符串是否出现过，然后按照长度从小到大排序。然后我们就可以从小到大将字符串加入到trie树中，当遇到节点不存在的情况，就把从这一位开始的字符串取出，判断这些字符串是否存在。举个栗子：a，hat，ahat这3个字符串，首先将a和hat放入trie树中。然后将ahat放入trie树中，当要放入h时，我们发现ah这个前缀不存在，，所以我们要把h作为一个字符串存起来，之后每放入一个字符，我们就更新所有的字符串，最终形成了hat这个字符串，经过预处理map["hat"]已经等于1，即已经存在了，那么我们就可以输出ahat。注意：这种方法有一个缺陷，就是处理aa，aaaa时会输出aaaa，所以我们要特判这种情况，当map["aa"]大于等于2时才能输出aaaa。
参考代码：
#include<map>#include<stack>#include<queue>#include<cmath>#include<vector>#include<cctype>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const double eps=1e-10;const int INF=0x3f3f3f3f;const int MAXN=50000+50;typedef long long LL;struct node{LL v;node* next[26];node(){v=0;memset(next,NULL,sizeof(next));}}*root;string word[MAXN];map<string,int>m;bool trie_insert(node* start,string word){int len=word.size();node* now=start;vector<string>v;v.clear();for(int i=0; i<len; i++){int id=word[i]-'a';if(now->next[id]==NULL)now->next[id]=new node();now=now->next[id];for(int j=0; j<v.size(); j++)v[j]+=word[i];if(now->v)v.push_back("");}now->v++;for(int i=0; i<v.size(); i++){if(m[v[i]]&&v[i]!=word){bool ok=true;int l=v[i].size();for(int j=1;j<l;j++){if(v[i][j]!=v[i][j-1]){ok=false;break;}}if(ok&&len==l*2&&m[v[i]]>=2)//特判aa，aaaareturn true;if(!ok||len!=l*2)return true;}}return false;}LL trie_query(node* start,char* word){int len=strlen(word);node* now=start;for(int i=0; i<len; i++){int id=word[i]-'a';if(now->next[id]==NULL)return 0;now=now->next[id];}return now->v;}void trie_del(node *now){for(int i=0; i<26; i++)if(now->next[i]!=NULL)trie_del(now->next[i]);delete now;}int main(){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endif // ONLINE_JUDGEint cnt=0;root=new node();while(cin>>word[++cnt]){if(m[word[cnt]]==0)m[word[cnt]]=1;elsem[word[cnt]]++;}cnt–;sort(word+1,word+1+cnt);for(int i=1; i<=cnt; i++)if(trie_insert(root,word[i]))cout<<word[i]<<endl;return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
思想如钻子，必须集中在一点钻下去才有力量
