首页 > 代码库 > HDU--2846--Repository--字典树

HDU--2846--Repository--字典树

2024-07-04 10:19:16   229人阅读

Repository

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2316    Accepted Submission(s): 882


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
 
题意：给出字典单词，然后给出字符串，求有多少字典单词包含这个字符串，a、d、dd和add在add都存在

题解：把每个字典单词分解插入字典树，比如abcd要分解成abcd、bcd、cd、d，这样不管是那一段都能查找到位


#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <malloc.h>
using namespace std;
struct ssss
{
    ssss *c[26];	//0到25分别是‘a‘到‘z‘
    int n,v;	//n:包含以当前字母结尾的某单词段的单词的个数。v:输入时标记最近是在第几个单词出现
}*s;	//根节点
void insert(char *str,int v)
{
    int i,j,k,l;
    ssss *p,*q;
    p=s;	//p从根节点开始进行插入
    for(i=0;str[i];i++)
    {
        k=str[i]-‘a‘;	//取字母对应的序号
        if(p->c[k]==NULL)	//如果相应位置的字母未插入则进行插入操作
        {
            q=(ssss *)malloc(sizeof(ssss));	//新建节点
            for(j=0;j<26;j++)	//初始化
            q->c[j]=NULL;
            q->n=1;
            q->v=v;
            p->c[k]=q;	//把新建的节点插入字典树
        }
        p=p->c[k];	//指向下一个节点
        if(p->v!=v)	//如果这个节点不是本次已经输入，这样就不会在同一个单词出现相同段重复插入了
        {
            p->v=v;	//标记为本次已经出入
            p->n++;	//个数加一
        }
    }
}
int find(char *str)
{
    int i,j,k,l;
    ssss *p;
    p=s;	//从根节点开始查找
    for(i=0;str[i];i++)
    {
        k=str[i]-‘a‘;	//去字母对应的序号
        if(p->c[k]==NULL)return 0;	//如果没有了，直接返回0
        p=p->c[k];	//不然继续向下一个节点跳转
    }
    return p->n;	//返回最后这个节点记录的个数，因为这次查找路径是以它结尾的
}
int main (void)
{
    int n,m,i,j,k,l,c,cc;
    char str[22];
    s=(ssss *)malloc(sizeof(ssss));	//根节点初始化
    for(i=0;i<26;i++)
    s->c[i]=NULL;
    s->n=0;
    s->v=-1;
    scanf("%d",&n);
    while(n--&&scanf("%s",str))
    {
        for(i=0; str[i]; i++)
        {
            insert(str+i,n);	//分成各个小段插入字典树
        }
    }
    scanf("%d",&n);
    while(n--&&scanf("%s",str))
    {
        printf("%d\n",find(str));
    }
    return 0;
}


联系
我们