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分鐘