Hat’s Words
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3224 Accepted Submission(s): 1223
Problem 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.
Input
Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 50,000 words.
Only one case.
Output
Your output should contain all the hat’s words, one per line, in alphabetical order.
Sample Input
a
ahat
hat
hatword
hziee
word
Sample Output
尼玛伤不起啊，分明是个模版题，结果写错初始化了，sind应该是1，写成了0，我擦
浪费我四十分钟，害我wa6遍，我擦
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <sstream>
#include <fstream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#include <iomanip>
using namespace std;
#include<string.h>
#define maxl 105
struct node
{
int next[26];
int count;
void init()
{
memset(next,-1,sizeof(next));
count=0;
}
} s[5000005];
char ss[50005][maxl];
//char ss1[50005][maxl];
/**//*struct node1
{
char s[16];
}ans[50005];*/
int num;
int sind,n;
void cas_init()
{
s[0].init();
sind=1;
}
/**//*int cmp(node1 ch1,node1 ch2)
{
return strcmp(ch1.s,ch2.s)<0;
}
*/
void ins(char str[])
{
int len=strlen(str);
int i,j,ind;
ind=0;
for(i=0; i<len; i++)
{
j=str[i]-'a';
if(s[ind].next[j]==-1)
{
s[sind].init();
s[ind].next[j]=sind++;
}
ind=s[ind].next[j];
}
s[ind].count++;
}
int search(char str[])
{
int len=strlen(str);
int ind,i,j;
ind=0;
for(i=0; i<len; i++)
{
j=str[i]-'a';
if(s[ind].next[j]==-1)
return 0;
else ind=s[ind].next[j];
}
if(s[ind].count>0) return 1;
else return 0;
}
int main()
{
char str[maxl],str1[maxl],str2[maxl];
cas_init();
n=0;
// freopen("in1.txt","r+",stdin);
while(scanf("%s",ss[n])!=EOF)
{
ins(ss[n]);
n++;
}
//int flag;
int i,j,k;
num=0;
for(i=0; i<n; i++)
{
//flag=0;
if(strlen(ss[i])==1) continue;
int len=strlen(ss[i]);
//printf("%d\n",len-1);
for(j=1; j<=len-1; j++)
{
for(k=0; k<j; k++) str1[k]=ss[i][k];
str1[k]='\0';
for(k=j; k<len; k++) str2[k-j]=ss[i][k];
str2[k-j]='\0';
//puts(str1);
//puts(str2);
if(search(str1)&&search(str2))
{
//flag=1;
//strcpy(ans[num++].s,ss[i]);
//strcpy(ss1[num++],ss[i]);
printf("%s\n",ss[i]);
break;
}
}
}
// sort(ans,ans+num,cmp);
//for(i=0;i<num;i++)
{
//printf("%s\n",ans[i].s);
// puts(ss[i]);
}
// fclose(stdin);
return 0;
}
/**//////尼玛，调半天都没调出来，浪费40分钟