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.
Solution
考虑用一颗trie记录所有出现过的单词，然后暴力拆分单词查询。长度实际只有100不会炸
Code
#include <stdio.h>
#include <string.h>
#define rep(i, st, ed) for (int i = st; i <= ed; i += 1)
#define N 100001
#define L 105
int mp[N][
26], T;
bool vis[N];
inline bool query(
int now,
int dep,
char st[],
int lim){
if (dep == lim){
return vis[now];
}
int tar = st[dep] -
'a';
if (!mp[now][tar]){
return 0;
}
return query(mp[now][tar], dep +
1, st, lim);
}
inline void ins(
int now,
int dep,
char st[],
int lim){
if (dep == lim){
vis[now] =
1;
return;
}
int tar = st[dep] -
'a';
if (!mp[now][tar]){
mp[now][tar] = ++ T;
}
ins(mp[now][tar], dep +
1, st, lim);
}
char st[N][L];
int main(
void){
int n =
0;
T =
0;
while (~
scanf(
"%s", st[++ n])){
int len =
strlen(st[n]);
ins(
0,
0, st[n], len);
}
rep(i,
1, n){
int len =
strlen(st[i]);
rep(j,
1, len -
1){
int a = query(
0,
0, st[i], j);
int b = query(
0, j, st[i], len);
if (a & b){
puts(st[i]);
break;
}
}
}
return 0;
}
