Hat’s Words
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1384 Accepted Submission(s): 506
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
題目分析 :
字典樹的題目, 這個題的方法比較暴力, 在輸入的時候將每個單詞都加入字典樹, 并用數組將所有的串都存起來來.
在輸入完成后, 對每個單詞進行拆分, 也就是暴力枚舉單詞不同位置的前后部分, 看在字典樹中是否存在, 存在即輸出.
不過貌似數據比較弱, 說是按字典順序輸出, 但其實他的輸入本就是按字典順序輸入的, 所以將排序也面了 , 呵呵.
另外,其實這題用STL 做更簡單, 當然追求效率除外.
trie 代碼:
/*
MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
http://www.cnblog.com/MiYu
Author By : MiYu
Test : 1
Program : 1247
*/
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef struct dictor DIC;
DIC *root = NULL;
struct dictor {
dictor (){ exist = false; memset ( child , 0 , sizeof ( child ) ); }
void insert ( char *ins );
bool find ( const char *ins );
private:
DIC *child[26];
bool exist;
};
void dictor::insert ( char *ins )
{
DIC *cur = root,*now;
int len = strlen ( ins );
for ( int i = 0; i < len; ++ i )
{
if ( cur->child[ ins[i] - 'a' ] != NULL )
{
cur = cur->child[ ins[i] - 'a' ];
}
else
{
now = new DIC;
cur->child[ ins[i] - 'a' ] = now;
cur = now;
}
}
cur->exist = true;
}
bool dictor::find ( const char *ins )
{
DIC *cur = root;
int len = strlen ( ins );
for ( int i = 0; i < len; ++ i )
{
if ( cur->child[ ins[i] - 'a' ] != NULL )
cur = cur->child[ ins[i] - 'a' ];
else
return false;
}
return cur->exist;
}
char words[50050][100];
char s1[100],s2[100];
DIC dict;
int main ()
{
root = &dict;
int n = 0;
while ( scanf ( "%s",words[n] ) != EOF )
{
dict.insert ( words[n++] );
}
for ( int i = 0; i < n; ++ i )
{
int len = strlen ( words[i] );
for ( int j = 1; j < len; ++ j )
{
memset ( s1, 0, sizeof ( s1 ) );
memset ( s2, 0, sizeof ( s2 ) );
strncpy ( s1, words[i], j );
strcpy ( s2, words[i]+j );
if ( dict.find ( s1 ) && dict.find ( s2 ) )
{
printf ( "%s\n", words[i] );
break;
}
}
}
//system ( "pause" );
return 0;
}
STL 代碼 :
/*
MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
http://www.cnblog.com/MiYu
Author By : MiYu
Test : 2
Program : 1247
*/
#include <iostream>
#include <string>
#include <map>
using namespace std;
map < string , int > mp;
string str[50005];
int main ()
{
int n = 0;
while ( cin >> str[n] ) mp[ str[n++] ] = 1;
for ( int i = 0; i < n; ++ i )
{
unsigned len = str[i].size ();
for ( unsigned j = 1; j < len; ++ j )
{
string s1 ( str[i], 0, j );
string s2 ( str[i], j );
if ( mp[s1] == 1 && mp[s2] == 1 )
{
cout << str[i] << endl;
break;
}
}
}
return 0;
}