题目大意
给定一些单词,要求你把所有的帽子单词找出来,如果某个单词恰好由另外两个单词连接而成,那么它就是帽子单词
题解
先把所有单词插入到Trie树,然后判断每个单词是不是帽子单词,做法就是:对于第i个单词,假设为s[0..n],枚举中间节点j,在Trie树上查询s[0..j]和s[j+1,…n]两个单词是否存在,存在的话说明它就是帽子词…WA了几发,找到帽子单词的时候忘记break了。。。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define MAXN 50005 char s[MAXN][30]; const int maxnode=MAXN*25+100; const int sigma_size=26; struct Trie { int ch[maxnode][sigma_size]; int val[maxnode]; int sz; Trie(){sz=1;val[0]=0;memset(ch[0],0,sizeof(ch[0]));} int idx(char c){return c-'a';} void insert(char *s,int v) { int u=0,n=strlen(s); for(int i=0;i<n;i++) { int c=idx(s[i]); if(!ch[u][c]) { memset(ch[sz],0,sizeof(sz)); val[sz]=0; ch[u][c]=sz++; } u=ch[u][c]; } val[u]=v; } bool find_prefix(const char *s,int len) { int u=0; for(int i=0;i<len;i++) { int c=idx(s[i]); if(!ch[u][c]) return false; u=ch[u][c]; } if(val[u]) return true; return false; } }; Trie trie; int main() { //freopen("sb.txt","r",stdin); //freopen("hehe.txt","w",stdout); int cnt=0; while(scanf("%s",s[cnt])!=EOF) trie.insert(s[cnt++],cnt); for(int i=0;i<cnt;i++) { int size=strlen(s[i]); for(int j=1;j<size-1;j++) { if(trie.find_prefix(s[i],j)&&trie.find_prefix(s[i]+j,size-j)) { printf("%s ",s[i]); break; } } } return 0; }