hdu1251 字典树trie 模板题

//字典树模板题.题意：给一个库，每次查询，求以之为前缀的单词数量。

#include<iostream>

#include<string>

#include<vector>

#include<cstdio>

#include<cstring>

using namespace std;

int tree[500000][27];

int w[500000];                  //记录结点属性。

int numv=0;               //  全局变量，记录顶点编号

int n;

void insert(string s)        //建树  tree[u][i]：结点u的第i个孩子（'a'为0，以此类推）.

{                           //值是i对应的孩子结点编号.这个要遍历孩子边，要遍历26次，

                           //否则添加vector<vector<> >，来保存边也可.

    int u=0;

    int len=s.size();

    for(int i=0;i<len;i++)

    {

        if(tree[u][s[i]-'a']==0)    //新建顶点

        {

            tree[u][s[i]-'a']=++numv;

        }

        u=tree[u][s[i]-'a'];     //往下找

        w[u]++;

    }

}

int find(string s)

{

    int u=0;

    int len=s.size();

    for(int i=0;i<len;i++)      //找不到

    {

        if(tree[u][s[i]-'a']==0)

           return 0;

        u=tree[u][s[i]-'a'];

    }

    return w[u];

}

int main()

{

    string s;

    while(1)          //一直读入字符串，到换行为止

    {

        cin>>s;

        insert(s);

        getchar();

        if(cin.peek()=='\n')break;

    }

    while(cin>>s)

    {

        cout<<find(s)<<endl;

    }

    return 0;

}
巴特西

hdu1251 字典树trie 模板题

最新文章

热门文章
