题目大意:
hat's word 的定义是字典中 恰好由另外两个单词连接起来的单词
给你一本字典，问有多少个hat‘s word,（字典按字典序给出）
单词数50000..
初步思路：
单词分为前缀单词，后缀单词
前缀单词出现在字典的前面，后缀单词出现在字典后面？
1.枚举前缀，哈希判断后缀？
复杂度：N^N*单词平均长度，显然不靠谱
2.trie树？
先建树，然后对于每一个单词读入，如果经过了某些单词结尾，判断一下后缀有没有.
复杂度似乎可靠？写写吧....
代码写成功..样例过..RE..字典树过大？.,..RE无数发 发现
int find_trie(char *s)
{
trie *root=TREE;
for(int i=0;s[i];i++)
{
int t=s[i]-'a';
if(root->next[t]==NULL) return 0;//写成root->next==NULL root=root->next[t];
}
if(root->flag==1) return 1;
else return 0;
}
</pre><p></p><p><span style="font-size:24px">已A.</span></p><p><span style="font-size:24px"></span></p><pre code_snippet_id="658096" snippet_file_name="blog_20150503_3_3616348" name="code" class="cpp">#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
using namespace std;
char buffer[50005][205];
struct trie{
trie *next[30];
int flag;
}TREE[200000],*EE;
void insert_trie(char *s)
{
trie *root=TREE;
for(int i=0;s[i];i++)
{
int t=s[i]-'a';
if(root->next[t]==NULL) { root->next[t]=EE++;}
root=root->next[t];
}
root->flag=1;
}
int find_trie(char *s)
{
trie *root=TREE;
for(int i=0;s[i];i++)
{
int t=s[i]-'a';
if(root->next[t]==NULL) return 0;
root=root->next[t];
}
if(root->flag==1) return 1;
else return 0;
}
void solve_trie(char *s)
{
int ok=0;
trie *root=TREE;
for(int i=0;s[i];i++)
{
int t=s[i]-'a';
root=root->next[t];
if(root->flag==1)
if(find_trie(s+i+1)==1)
{
ok=1;
break;
}
}
if(ok) printf("%s\n",s);
}
void Clear()
{
memset(TREE,0,sizeof(TREE));
EE=TREE+1;
}
void init()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
int main()
{
int p=0;
// init();
Clear();
while(scanf("%s",buffer[++p])!=EOF)
insert_trie(buffer[p]);
for(int i=1;i<=p;i++)
{
solve_trie(buffer[i]);
}
return 0;
}