字典樹 模闆

建立字典樹，求以……為字首的單詞個數

統計難題

問題描述：

lgnatius最近遇到一個難題，老師交給他很多單詞（隻有小寫字元組成，不會有重複的單詞出現），現在老師要他統計出以某個字元串為字首的字元數量（單詞本身也是自己的字首）。

輸入：

輸入資料的第一部分是一張單詞表，單詞的長度不超過10，它們代表的是老師交給lgnatius統計的單詞，一個空行代表單詞表的結束。第二部分是一連串的提問，每行一個提問，每個提問都是字元串。

注意：本題隻有一組測試資料，處理到檔案結束

輸出：

對于每個提問，給出以該字元串為字首的單詞數量。

Sample Input:

banana

band

bee

absolute

acm

ba

b

band

abc

Sample Output:

2

3

1

#include<cstdio>
#include<cstring>
using namespace std;
int n, m, ans;
char str[];
struct dic_tree  //構造字典樹，26叉樹，根節點為空
{
    dic_tree *node[]; //26個節點
    int num; // record the num of child
    bool terminal; //表示該結點位置是否是單詞的結束位
    dic_tree()  // 構造函數，初始化終點情況與結點
    {
        for(int i; i<; ++i)
        {
            node[i] = NULL; // 初始化空結點， node[0]表示‘a’在單詞中
            terminal = ;
            num = ;
        }
    }
}*root; //樹是通過指針形式表達的

void build(dic_tree *p, char str[], int end) // 生成字典樹的函數
{
    int ix = ;
    p->num++;
    while(ix < end)  // 循環直到讀完單詞最後一個字母
    {
        int c = str[ix] - 'a';
        if(p->node[c])  // 如果到node[c]連通
        {
            p = p->node[c];
            if(ix == end - )
                 p->terminal = ;
             ++ix;
        }
        else
        {
            p->node[c] = new dic_tree;  //如果不通，則在該結點生成一個26叉樹
            p = p->node[c];
            if(ix == end - )
                 p->terminal = ;
             ++ix;
        }
        p->num++;
    }
}

int search(dic_tree *p, char str[], int end)
{
    int ix = ;
    while(ix < end)
    {
        int c = str[ix] - 'a';
        if(p->node[c])
        {
            p=p->node[c];
            if(ix == end-)
            {
                p->terminal = ;
                return p->num;
            }
            ++ix;
        }
        else return ;
    }
}

int main()
{
    // freopen("in.txt", "r", stdin);
    root = new dic_tree;
    while(gets(str)&&str[]!='/0')
    {
        bulid(root, str, strlen); // 生成字典樹
    }
    while(scanf("%s", str) != EOF)
        printf("%d/n",search(root, str, strlen(str))); //搜尋字典樹
    return ;
}
           

當然，這道題還可以用map，隻是時間較長：(^__^)

#include<iostream>  
#include<map>  
#include<string>  
using namespace std;  
int main()  
{  
    int i,j,k,len;  
    string str;char temp[],temp1[];  
    map <string,int> mymap;  
    while(gets(temp))  
    {  
        if(temp[]=='/n') break;  
        len=strlen(temp);  
        if(len==) break;  
        for(i=;i<len;i++)//求出某個字元串的所有字首,并用MAP存起來  
        {  
            for(j=;j<=i;j++) temp1[j]=temp[j];temp1[j]='/0';  
            str.assign(temp1);  
            mymap[str]++;  
        }  
    }  
    while(scanf("%s",&temp)!=EOF)  
        cout<<mymap[temp]<<endl;//此時直接輸出結果即可  
    return ;  
}