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.
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.
For each query, you just output the number of the
merchandises, whose names contain the search string as their substrings.
0
20
11
11
2
思路：把每个单词X1X2X3……分别以X1，X2，X3为开头存入字典树中，然后要进行标记，同一个单词不能多次计数
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#define
MAX 26
using namespace std;
struct tree
{
struct
tree *child[26];
int
v;//记录包含该结点的单词个数
int
flag; //最后一次经过此结点的商品ID
}*root;
void init()
{
int i;
root=(struct tree*)malloc(sizeof(struct
tree));
for(i=0; i<26; i++)
{
root->child[i]=0;
root->v=0;
root->flag=-1;
}
return
;
}
void build(char *str,int d)
{
int
id,i,j,len;
len=strlen(str);
struct
tree *p=root,*q;
for(i=0; i<len;
i++)
{
id=str[i]-‘a‘;
if(p->child[id]==0)
{
q=(struct tree*)malloc(sizeof(struct
tree));
for(j=0; j<26;
j++)
q->child[j]=0;
p->child[id]=q;
p=p->child[id];
p->v=0;
p->flag=-1;
}
else
p=p->child[id];
if(p->flag!=d)//如果当前结点的商品编号不等于要插入商品的编号，则计数器v++，并且重新置编号的值
{
p->flag=d;
p->v++;
}
}
}
int find(char *str)
{
int
len=strlen(str);
int i,j,id;
struct
tree *p=root,*q;
for(i=0; i<len;
i++)
{
id=str[i]-‘a‘;
if(p->child[id]==0)
return 0;
p=p->child[id];
}
return
p->v;
}
int main()
{
int
i,j,len,tt,t;
char a[105],b[105];
scanf("%d",&tt);
init();
for(i=0;i<tt;i++)
{
scanf("%s",b);
len=strlen(b);
for(j=0; j<len;
j++)
build(b+j,i);//将字符串X=X1X2...Xn的分别以X1,X2...Xn开头的后缀字符串插入到tree树中
}
scanf("%d",&t);
for(i=0;
i<t; i++)
{
scanf("%s",a);
printf("%d\n",find(a));
}
return
0;
}
