題目分析:
剛學(xué)字典樹(shù) ,也就是 trie 樹(shù), 教程很容易看明白, 1251 是一道很明顯的 模板題, 看過(guò) PPT 后 直接敲代碼 1A.
第一次做, 順便介紹下 trie樹(shù) :
字典樹(shù)（Trie）是一種用于快速字符串檢索的多叉樹(shù)結(jié)構(gòu)。其原理是利用字符串的公共前綴來(lái)降低時(shí)空開(kāi)銷(xiāo),從而達(dá)到提高程序效率的目的。
它有如下簡(jiǎn)單的性質(zhì)：
(1) 根節(jié)點(diǎn)不包含字符信息；
(3) 一棵m度的Trie或者為空，或者由m棵m度的Trie組成。
搜索字典項(xiàng)目的方法為：
(1) 從根結(jié)點(diǎn)開(kāi)始一次搜索；
(2) 取得要查找關(guān)鍵詞的第一個(gè)字母，并根據(jù)該字母選擇對(duì)應(yīng)的子樹(shù) 并轉(zhuǎn)到該子樹(shù)繼續(xù)進(jìn)行檢索；
(3) 在相應(yīng)的子樹(shù)上，取得要查找關(guān)鍵詞的第二個(gè)字母，
并進(jìn)一步選擇對(duì)應(yīng)的子樹(shù)進(jìn)行檢索。
(4) 迭代過(guò)程……
(5) 在某個(gè)結(jié)點(diǎn)處，關(guān)鍵詞的所有字母已被取出，則讀取
附在該結(jié)點(diǎn)上的信息，即完成查找。
代碼如下 :
當(dāng)然也可以拿來(lái)做模板 , 
/*
MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋
http://www.cnblog.com/MiYu
Author By : MiYu
Test : 1
Program : 1251
*/
#include <iostream>
using namespace std;
typedef struct dict DIC;
struct dict {
dict (){ n = 0; memset ( child , 0 , sizeof ( child ) ); }
void insert ( char *ins )
{
DIC *cur = this,*now;
int len = strlen ( ins );
if ( len == 0 ) return ;
for ( int i = 0; i != len; ++ i )
{
if ( cur->child[ ins[i] - 'a' ] != NULL )
{
cur = cur->child[ ins[i] - 'a' ];
cur->n ++;
}
else
{
now = new DIC;
cur->child[ ins[i] - 'a' ] = now;
now->n ++;
cur = now;
}
}
}
int find ( char *ins )
{
DIC *cur = this;
int len = strlen ( ins );
if ( 0 == len ) return 0;
for ( int i = 0; i != len; ++ i )
{
if ( cur->child[ ins[i] - 'a' ] != NULL )
cur = cur->child[ ins[i] - 'a' ];
else
return 0;
}
return cur->n;
}
private:
DIC *child[26];
int n;
};
char word[11];
int main ()
{
DIC dict;
while ( gets ( word ), strcmp ( word, "") != 0 )
dict.insert ( word );
char qur[11];
while ( scanf ( "%s",qur ) != EOF )
{
printf ( "%d\n",dict.find ( qur ) );
}
return 0;
}