MiYu原创, 转帖请注明 : 转载自
______________白白の屋
题目地址 :
http://acm.hdu.edu.cn/showproblem.php?pid=1247
题目描述:
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
You are to find all the hat’s words in a dictionary.
Only one case.
a
ahat
hat
hatword
hziee
word
ahat
hatword
题目分析 :
字典树的题目, 这个题的方法比较暴力, 在输入的时候将每个单词都加入字典树, 并用数组将所有的串都存起来来.
在输入完成后, 对每个单词进行拆分, 也就是暴力枚举单词不同位置的前后部分, 看在字典树中是否存在, 存在即输出.
不过貌似数据比较弱, 说是按字典顺序输出, 但其实他的输入本就是按字典顺序输入的, 所以将排序也面了 , 呵呵.
另外,其实这题用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;
}
