MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自?
______________白白の屋
??
??
?
題目地址 :
?? ? 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
題目分析 :
??
?? ? ? ?字典樹的題目, 這個(gè)題的方法比較暴力, ?在輸入的時(shí)候?qū)⒚總€(gè)單詞都加入字典樹, ?并用數(shù)組將所有的串都存起來來.
在輸入完成后, ?對每個(gè)單詞進(jìn)行拆分, 也就是暴力枚舉單詞不同位置的前后部分, 看在字典樹中是否存在, 存在即輸出.
不過貌似數(shù)據(jù)比較弱, 說是按字典順序輸出, 但其實(shí)他的輸入本就是按字典順序輸入的, 所以將排序也面了 , 呵呵.
?? ?另外,其實(shí)這題用STL 做更簡單, 當(dāng)然追求效率除外.
trie 代碼:
?/*
MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
?? ? ? ? ?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原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
?? ? ? ? ?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;
}
?
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
