HDU1251

题目大意

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

题解

把单词插入到Trie树中，Trie树的每个结点记录以此结点结尾的单词前缀出现的次数，每次把进行单词插入的时候把沿途经过的结点+1即可

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxnode=3000005;
const int sigma_size=26;
struct Trie
{
       int ch[maxnode][sigma_size];
       int  val[maxnode];
       int sz;
       Trie(){sz=1;memset(val,0,sizeof(val));memset(ch[0],0,sizeof(ch[0]));}
       int idx(char c){return c-'a';}
       void insert(char *s)
       {
             int u=0,n=strlen(s);
             for(int i=0;i<n;i++)
             {
                    int c=idx(s[i]);
                    if(!ch[u][c])
                    {
                        memset(ch[sz],0,sizeof(ch[sz]));
                        val[sz]++;
                        ch[u][c]=sz++;
                    }
                    else
                    val[ch[u][c]]++;
                    u=ch[u][c];
             }
       }
       int find_prefixes(const char *s)
       {
            int u=0,n=strlen(s);
            for(int i=0;i<n;i++)
            {
                int c=idx(s[i]);
                  if(!ch[u][c]) return 0;
                  u=ch[u][c];
            }
            return val[u];
       }
};
Trie trie;
int main()
{
    char word[15];
    while(gets(word)&&word[0]!='')
         trie.insert(word);
    while(scanf("%s",word)!=EOF)
          printf("%d
",trie.find_prefixes(word));
    return 0;
}