hdu 2846 Repository (字典树)

解题大意: 给出单词的词典，然后有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;  
}

补充：软件开发 , C++ ,