HDU 1247 Hat's Words （字典树）

HDU 1247 Hat's Words （字典树）

【题目链接】​​click here~~​​

【题目大意】A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary. ，找出由两个子字符串组成的字符串。

【解题思路】字典树

#include using namespace std;const int N=5*1e4+100;const int MOD=998244353;#pragma comment(linker,"/STACK:102400000,102400000")int n,m,k,tot;char word[N][27];typedef long long LL;struct dictree{ int count; bool ok; dictree *tree[27]; dictree() { ok=false; memset(tree,0,sizeof(tree)); }};void insert(dictree *head,char str[]){ dictree *p=head; int i=0; while(str[i]) { int k=(int)(str[i++]-'a'); if(p->tree[k]==NULL) p->tree[k]=new dictree(); p=p->tree[k]; } p->ok=true;}bool search(dictree *head,char str[]){ int i=0,top=0,num[N]; dictree *p=head; while(str[i]) { int k=(int)str[i++]-'a'; if(p->tree[k]==NULL) return false; p=p->tree[k]; if(p->ok&&str[i]) num[top++]=i; } while(top) { bool okk=true; i=num[--top]; p=head; while(str[i]) { int k=(int)str[i++]-'a'; if(p->tree[k]==NULL) { okk=false; break; } p=p->tree[k]; } if(okk&&p->ok) return true; } return false;}int main(){ int len=0; dictree *head=new dictree(); while(gets(word[len])) { insert(head,word[len]); len++; } for(int i=0; i

set容器:

#include using namespace std;int main(){ string str; setsa,sb; while(cin>>str) sa.insert(str); set::iterator be=sa.begin(),en=sa.end(),op,opp; for(; be!=en; be++) { int Count=be->size(); for(op=be,op++; op!=en; op++) { if(be->compare(op->substr(0,Count))==0) { if(sa.count(op->substr(Count,op->size()-Count))) sb.insert(*op); } else break; } } for(opp=sb.begin(); opp!=sb.end(); opp++) cout<<*opp<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。