HDU 2846 Repository


		Repository
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1750    Accepted Submission(s): 651
 
 
Problem Description
When you go shopping, you can search in repository for avalible merchandises by the computers and internet. First you give the search system a name about something, then the system responds with the results. Now you are given a lot merchandise names in repository and some queries, and required to simulate the process.
 
 
Input
There is only one case. First there is an integer P (1<=P<=10000)representing the number of the merchanidse names in the repository. The next P lines each contain a string (it's length isn't beyond 20,and all the letters are lowercase).Then there is an integer Q(1<=Q<=100000) representing the number of the queries. The next Q lines each contains a string(the same limitation as foregoing descriptions) as the searching condition.
 
 
Output
For each query, you just output the number of the merchandises, whose names contain the search string as their substrings.
 
 
Sample Input
20
ad
ae
af
ag
ah
ai
aj
ak
al
ads
add
ade
adf
adg
adh
adi
adj
adk
adl
aes
5
b
a
d
ad
s
 
 
Sample Output
0
20
11
11
2
 
 
Source
2009 Multi-University Training Contest 4 - Host by HDU
 
 
Recommend
gaojie
 解题思路：字典树第三弹，这一题要求我们找到输入的词是字典中多少个词的子串，而不仅仅是其前缀，因此建树的时候需要将词典中词分解成不同前缀加入到树中，即是说将形如abc的词拆成abc,bc,c,三种形式，这样就相当于找输入的词是词典中多少词的前缀，需要注意的是，对于同一个词分解出的多个前缀，如果他们之间有相同的话，这种前缀，只算作一种，即是说形如abca之类的词，会分解出abca,a两种前缀，但因为是同一个词分解出来的，所以算作一种。判断是否是同一个词分解出来的需要给每个输入的词及其分解出的前缀加以相同的id进行编号。
[cpp]  
#include<cstdio>  
#include<cstring>  
#include<iostream>  
using namespace std;  
int ans,len;  
typedef struct TrieNode  
{  
    int c,id;  
    struct TrieNode *next[26];  
    TrieNode()  
    {  
        id=-1;//初始化每个节点的id为-1  
        c=0;  
        memset(next,0,sizeof(next));  
    }  
};  
  
TrieNode *root=NULL;  
void CreatTree(char s[],int num)  
{  
    int i,len;  
    len=strlen(s);  
    TrieNode *p=root;  
    TrieNode *temp;  
    for(i=0;i<len;i++)  
    {    www.zzzyk.com
        if(p->next[s[i]-'a']==NULL)  
        {  
            temp=new TrieNode;  
            p->next[s[i]-'a']=temp;  
        }  
        p=p->next[s[i]-'a'];  
        if(p->id!=num)//如果分解出的词的前缀与已经在之前分解的词的前缀相同(id==num)，那就不能算作一种新的前缀  
           p->c++;  
        p->id=num;//对同一个词分解出的词，在树上的各个节点给予相同id  
    }  
}  
void Search(char s[],int d)  
{  
    int i,j;  
    TrieNode *p=root;  
    for(i=0;i<d;i++)  
    {  
        if(p->next[s[i]-'a'])  
            p=p->next[s[i]-'a'];  
        else  
        {  
            ans=0;//如果输入的词不是词典中任何词及其分解出的词的前缀，那这个词就不是词典中任何一个词的子串  
            return;  
        }  
    }  
    ans=p->c;//否则，在不同词的分解的词（重复的不算）中，输出的词是多少个词的前缀就是所求答案  
}  
void Delete(TrieNode *node)  
{  
    int i;  
    for(i=0;i<26;i++)  
    {  
        if(node->next[i])  
            Delete(node->next[i]);  
        delete node->next[i];  
        node->next[i]=0;  
    }  
}  
int main()  
{  
    int i,j,m,n,len;  
    char str[25],temp[25];  
    root=new TrieNode;  
    scanf("%d",&n);  
    memset(str,'\0',sizeof(str));  
    for(i=0;i<n;i++)  
    {  
        scanf("%s",&str);  
        len=strlen(str);  
        for(j=0;j<len;j++)  
        {  
            strncpy(temp,str+j,len-j);//将词典中词以不同前缀进行分解，并分别加入树中  
            temp[len-j]='\0';  
            CreatTree(temp,i);//i用以判断是否为词典中同一个词分解出来的  
        }  
        memset(str,'\0',sizeof(str));  
    }  
    scanf("%d",&m);  
    for(i=0;i<m;i++)  
    {   www.zzzyk.com
        ans=0;  
        scanf("%s",&str);  
        len=strlen(str);  
        Search(str,len);  
        printf("%d\n",ans);  
    }  
    Delete(root);  
    return 0;  
}

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