字典樹（Trie Tree）的應用舉例

字典樹是一種很牛的字符串操作算法，可以在短時間內完成字符串的插入、刪除、查找等功能，是NOIP、NOI必備資料之一。

關於字典樹的具體算法可以到維基百科 上學習，這裡我僅僅通過舉例來說明如何運用字典樹。


例題：

题目名	scanword
输入文件名	scanword.in
输出文件名	scanword.out
时间限制	1000 ms
内存限制	128 MB

全国英语四级考试就这样如期来了，可是小 y 依然没有做好充分准备。为了能够大学毕业可怜的小 y 决定作弊。
小 y 费尽心机，在考试的时候夹带了一本字典进考场，但是现在的问题是，考试的时候可能有很多的单词要查，小 y 能不能来得及呢？
输入格式：
第一行一个整数 N ，表示字典中一共有多少个单词（ N<=10000 ）。
接下来每两行表示一个单词，其中：
第一行是一个长度 <=100 的字符串，表示这个单词，全部小写字母，单词不会重复。
第二行是一个整数，表示这个单词在字典中的页码。
接下来是一个整数 M ，表示要查的单词数 (M<=10000) 。
接下来 M 行，每行一个字符串，表示要查的单词，保证在字典中存在。
输出格式：
M 行，每行一个整数，表示第 I 个单词在字典中的页数。
输入样例：
2
scan
10
word
15
2
scan
word
输出样例
10
15

這是一道基礎的字典樹的應用題，以下是我的代碼，十分簡單易懂，適合參加各種OI的選手。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

const int sonnum=26;
const char base='a';
class Trie
{
public:
    bool isStr;
    int Page;
    class Trie *son[sonnum];
};

Trie *NewTrie()
{
    Trie *temp=new Trie;
    temp->isStr=false;
    for (int i=0;i<sonnum;i++)
        temp->son[i]=NULL;
    return temp;
}

void InsertStr(Trie *pnt,char *s,unsigned int len,int P)
{
    Trie *temp=pnt;
    for (unsigned int i=0;i<len;i++)
    {
        if (temp->son[s[i]-base]==NULL)
            temp->son[s[i]-base]=NewTrie();
        temp=temp->son[s[i]-base];
    }
    temp->isStr=true;
    temp->Page=P;
}

int GetPage(Trie *pnt,char *s,unsigned int len)
{
    Trie *temp=pnt;
    for (unsigned int i=0;i<len;i++)
        temp=temp->son[s[i]-base];
    return temp->Page;
}

Trie *pnt=NewTrie();

void init()
{
    int N;
    cin>>N;
    for (int i=1;i<=N;i++)
    {
        char STR[101];
        int p;
        cin>>STR>>p;
        InsertStr(pnt,STR,strlen(STR),p);
    }
    cin>>N;
    for (int i=1;i<=N;i++)
    {
        char STR[101];
        cin>>STR;
        cout<<GetPage(pnt,STR,strlen(STR))<<endl;
    }
}

int main()
{
   
    freopen("scanword.in","r",stdin);
    freopen("scanword.out","w",stdout);
    init();
    fclose(stdin);
    fclose(stdout);
    return 0;
}