野蛮的城管时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 181920 KByte
总提交 : 21 测试通过 : 4 描述
在传说中的粉刷街上，墙上充斥着各种各样的彩色词汇。 但在这条街上，新任城管chc突然野蛮的认定了某些词汇是不应该存在的，于是要求RSS将那些词汇统计数量并上报。 当然chc的风骚你们是不懂的，他要求RSS只要看到任何一个单词中包含该词汇就必须统计上，比如babs中就会被认定为含有abs这个单词。 现在邪恶的CHC想知道 RSS统计某个词汇的数量。 被痛苦摧残的RSS请求你的帮助。
输入
第一行是个数字N，代表这条街上有N个词汇。 接下来N行，每行有一个字符串。 接下来一行是一个整数M，表示有M次统计。 然后是M行字符串，代表需要被统计的单词。 （1<=N<=10000，1<=M<=100000，字符串长度不超过20，但大小写敏感）
输出
对应每次统计，输出一次城管们的统计数字。 样例输入 4 样例输出 4 题目来源 HLY |
怪叔叔改编的题~ 嘿嘿
又是一道字典树水题~~
http://218.194.91.48/acmhome/problemdetail.do?&method=showdetail&id=1308
只需在建立字典树的时候，每一次到达节点，使节点计数器num++
但这样还是会错哟~~ 因为它问的是不同单词的个数，而同一个单词可能包含有某 子串 很多遍~~
因此，需要特判一下，建树时，每个num++的节点，需要判断是否同一个单词，如果是，则不重复执行num++
具体看代码~~
#include<iostream>
#include<cstdio>
using namespace std;
char str[30];
int s[30];
struct Point{
int num,n;
Point *next[52];
};
Point *root;
void init_(Point *x){
x->num=0;
x->n=-1;
for(int i=0;i<52;i++) x->next[i]=0;
}
void deal(){
for(int i=0;str[i];i++)
if(str[i]>='a') s[i]=str[i]-'a';
else s[i]=str[i]-39;
}
void add(int n){
Point *p,*now;
int i,j;
deal();
for(i=0;str[i];i++){
now=root;
for(j=i;str[j];j++){
if(!now->next[s[j]]){
p=new Point;
init_(p);
now->next[s[j]]=p;
}
now=now->next[s[j]];
if(now->n!=n){
now->num++;
now->n=n;
}
}
}
}
int qry(){
Point *p,*now=root;
int i;
deal();
for(i=0;str[i];i++){
if(!now->next[s[i]]) break;
now=now->next[s[i]];
}
if(!str[i])
return now->num;
else return 0;
}
int main(){
int n;
while(~scanf("%d",&n)){
root=new Point;
init_(root);
while(n--){
scanf("%s",str);
add(n);
}
scanf("%d",&n);
while(n--){
scanf("%s",str);
printf("%d\n",qry());
}
}
return 0;
}