学步园

题目链接:   hdu 2846

解题大意: 
 给出单词的词典，然后有N次查询

                  每次查询是给出的字符串是词典中多少个单词的子串

解题思路: 
 将每个单词的长度1到Tlen长度为T的子串存进字典树

                  如单词abacab，只要存abacab，bacab，acab，cab，ab，b

                  如果所有的子串都存进去的话，查询的结果会重复

                  树中每个结点w值代表经过该结点的次数，同一个单词的子串仅+1

                  查询的时候最后一个字符结点的w值既是答案

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 10010
struct snode{
    int flag,w;
    int next[26];  //第一种写法
}Tree[MAX*50];
char ch1[30],ch[30];
int Index;
void Insert(int Tlen,int k)  //遍历插入字典树
{
    int i,S=0,child;
    for(i=1;i<=Tlen;i++)
    {
        child=ch[i-1]-'a';
        if(Tree[S].next[child]==0)  //结点不存在则建立新节点
        {
            Tree[Index].flag=k,Tree[Index].w=1;
            Tree[S].next[child]=Index++;
        }
        else
        {
            if(Tree[Tree[S].next[child]].flag!=k) //不是同一单词+1
            {
                Tree[Tree[S].next[child]].flag=k;
                Tree[Tree[S].next[child]].w++;
            }
        }
        S=Tree[S].next[child];
    }
}

int Query(int Tlen)          //遍历查询字典树
{
    int i,S=0,child;
    for(i=1;i<=Tlen;i++)
    {
        child=ch[i-1]-'a';
        if(Tree[S].next[child]!=0)
        {
            if(i==Tlen)      //返回最后一个字符的w值
            {
                return Tree[Tree[S].next[child]].w;
            }
            S=Tree[S].next[child];
        }
        else
            return 0;
    }
}

int main()
{
    int n,i,j,j1,TTlen;
    Index=1;
    memset(Tree,0,sizeof(Tree));
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%s",ch1);
        TTlen=strlen(ch1);
        for(j=0;ch1[j];j++)
        {
            for(j1=0;ch1[j1+j];j1++) //分别以1..Tlen开头的子串
            {
                ch[j1]=ch1[j1+j];
            }
            ch[j1]='\0';
            Insert(TTlen-j,i+1);  //单词的子串建树
        }
    }
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%s",ch);
        printf("%d\n",Query(strlen(ch)));  //查询
    }
    return 0;
}