一个很经典的字典树题目
先建树 再拆单词进行判断是否都在树内
因为爆内存错了很久
如果一个四十万的数组 用mamset的话会直接爆几十万的内存
所以要：用多少 初始化多少才对！（ 修改了两条初始化语句 见代码） 不过这题只有一组数据 所以不初始化关系不大
#include<bits/stdc++.h>
using namespace std; int trie[][]={};
int sum[];
char ans[][];//这里数组开小了导致一直wa
int root=;
int pos=;
void insert1(char *s)
{
int root=;
for(int i=;i<strlen(s);i++)
{ int ch=s[i]-'a';
if( trie[ root ][ch]== )
{ memset(trie[pos],,sizeof(trie[pos]));//用多少初始化多少
trie[root][ch]=pos++; }
root=trie[root][ch];
}
sum[root]=;
} bool find1(char *s)
{
int root=;
for(int i=;i<strlen(s);i++)
{
int ch=s[i]-'a';
if( trie[root][ch]== )return false;
root=trie[root][ch]; }
return sum[root]; } int main()
{ int c=;
pos=;
memset(sum,,sizeof(sum));
memset(trie[],,sizeof(trie[]));//用多少初始化多少
while(gets(ans[c++]))
{
insert1( ans[c-] );
} for(int i=;i<=c-;i++)
{ for(int k=;k<strlen( ans[i] ) ;k++)
{
char a[],b[];
strncpy(a,ans[i],k );a[k]='\0';
strncpy(b,ans[i]+k, strlen(ans[i]) );
b[strlen(ans[i]) -k]='\0';
if(find1(b)&&find1(a))
{
puts(ans[i]);break; }
} } return ;
}