題目分析:
剛學(xué)字典樹 ,也就是 trie 樹, 教程很容易看明白, 1251 是一道很明顯的 模板題, 看過 PPT 后 直接敲代碼 1A.
第一次做, 順便介紹下 trie樹 :
字典樹（Trie）是一種用于快速字符串檢索的多叉樹結(jié)構(gòu)。其原理是利用字符串的公共前綴來降低時空開銷,從而達到提高程序效率的目的。
它有如下簡單的性質(zhì)：
(1) 根節(jié)點不包含字符信息；
(3) 一棵m度的Trie或者為空，或者由m棵m度的Trie組成。
搜索字典項目的方法為：
(1) 從根結(jié)點開始一次搜索；
(2) 取得要查找關(guān)鍵詞的第一個字母，并根據(jù)該字母選擇對應(yīng)的子樹 并轉(zhuǎn)到該子樹繼續(xù)進行檢索；
(3) 在相應(yīng)的子樹上，取得要查找關(guān)鍵詞的第二個字母，
并進一步選擇對應(yīng)的子樹進行檢索。
(4) 迭代過程……
(5) 在某個結(jié)點處，關(guān)鍵詞的所有字母已被取出，則讀取
附在該結(jié)點上的信息，即完成查找。
代碼如下 :
當(dāng)然也可以拿來做模板 , 
/*
MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(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;
}