题目分析:
刚学字典树 ,也就是 trie 树, 教程很容易看明白, 1251 是一道很明显的 模板题, 看过 PPT 后 直接敲代码 1A.
第一次做, 顺便介绍下 trie树 :
字典树（Trie）是一种用于快速字符串检索的多叉树结构。其原理是利用字符串的公共前缀来降低时空开销,从而达到提高程序效率的目的。
它有如下简单的性质：
(1) 根节点不包含字符信息；
(3) 一棵m度的Trie或者为空，或者由m棵m度的Trie组成。
搜索字典项目的方法为：
(1) 从根结点开始一次搜索；
(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树 并转到该子树继续进行检索；
(3) 在相应的子树上，取得要查找关键词的第二个字母，
并进一步选择对应的子树进行检索。
(4) 迭代过程……
(5) 在某个结点处，关键词的所有字母已被取出，则读取
附在该结点上的信息，即完成查找。
代码如下 :
当然也可以拿来做模板 , 
/*
MiYu原创, 转帖请注明 : 转载自 ______________白白の屋
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;
}