hdu2846 字典树(带id的)

思路：

      一开始想到hash,但是因为用的是map，所以超时了，map的操作是有代价的，他本身还会排序的，所以超时了，想用vec结果还没弄出来这个类型hash["aaa"] = 1,最后只能字典树了，先想下字典树，字典树处理前缀的出现的次数的时候非常拿手的，对于这个题目，我们可以把每个串都拆开，拆成一个一个的，然后在把他们加在树里面，这样就OK了，还有一个关键的地方，就是比如拆这个串 aa 可以拆成 a ,a ,aa，所以我们要在第一个a的时候只累加一次，怎么做到呢，可以在Tree的结构体里面在开个变量，标记当前这个字母最后一次是被谁更新的，如果是自己，那么就不会V++.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct Tree
{
    Tree *next[26];
    int v ,mk;
}Tree;

Tree root;

void Buid_Tree(char *str ,int mkk)
{
    int len = strlen(str);
    Tree *p = &root ,*q;
    for(int i = 0 ;i < len ;i ++)
    {
        int id = str[i] - 'a';
        if(p -> next[id] == NULL)
        {
           q = (Tree *) malloc(sizeof(root));
           q -> v = 1;
           q -> mk = mkk;
           for(int j = 0 ;j < 26 ;j ++)
           q -> next[j] = NULL;
           p -> next[id] = q;
           p = p -> next[id];

        }
        else
        {
            p = p -> next[id];
            if(p -> mk != mkk) p -> v ++;
            p -> mk = mkk;
        }
   }
}

int Find(char *str)
{
    int len = strlen(str);
    Tree *p = &root;
    for(int i = 0 ;i < len ;i ++)
    {
       int id = str[i] - 'a';
       p = p -> next[id];
       if(p == NULL) return 0;
    }
    return p -> v;
}

int main ()
{
    char str[25];
    int n ,m ,i;
    while(~scanf("%d" ,&n))
    {
        for(i = 0 ;i < 26 ;i ++)
        root.next[i] = NULL;
        for(i = 1 ;i <= n ;i ++)
        {
            scanf("%s" ,str);
            int len = strlen(str) - 1;
            for(int ii = 0 ;ii <= len ;ii ++)
            {
                char now[25];
                for(int jj = 0 ;jj + ii <= len ;jj ++)
                {
                   now[jj] = str[ii + jj];
                   now[jj+1] = ' ';
                   Buid_Tree(now ,i);
                }
            }
         }
         scanf("%d" ,&m);
         for(i = 1 ;i <= m ;i ++)
         {
            scanf("%s" ,str);
            printf("%d
" ,Find(str));
          }
     }
     return 0;
}