/* 这题倒是没啥难度 字典树可搞 但是吧 空间是个问题 开始写成这样 struct node { int next[27],sum[27]; bool over; }t[maxn]; 死活过不了 开小了er 开大了MLE 问了问wmy 很机智的说用map 管用的 然后卡空间过了 看他们用指针动态分配内存 然而我并不太会..... */ #include<iostream> #include<cstdio> #include<cstring> #include<map> #define maxn 480010 using namespace std; int topt; char s[20]; struct node { map<int,int>next,sum; bool over; }t[maxn]; void Add_tree() { int now=0,l=strlen(s); for(int i=0;i<l;i++) { int x=s[i]-'a'+1; if(t[now].next[x]) { t[now].sum[x]++; now=t[now].next[x]; } else { topt++;t[now].next[x]=topt; t[now].sum[x]++;now=topt; } } } int find_tree() { int ans=0,p=0,now=0,l=strlen(s),x,pre; while(p<=l-1) { x=s[p]-'a'+1; if(t[now].next[x])pre=now,now=t[now].next[x],p++; else return 0; } return t[pre].sum[x]; } int main() { while(gets(s)&&strlen(s))Add_tree(); while(gets(s))cout<<find_tree()<<endl; return 0; }
/* 恩 之前一直纠结空间 因为状态写错了 可以不用那么多.... */ #include<iostream> #include<cstdio> #include<cstring> #include<map> #define maxn 500010 using namespace std; int topt; char s[20]; struct node { int next[27],sum; }t[maxn]; void Add_tree() { int now=0,l=strlen(s); for(int i=0;i<l;i++) { int x=s[i]-'a'+1; if(t[now].next[x])now=t[now].next[x]; else { topt++;t[now].next[x]=topt;now=topt; } t[now].sum++; } } int find_tree() { int ans=0,p=0,now=0,l=strlen(s); while(p<=l-1) { int x=s[p]-'a'+1; if(t[now].next[x])now=t[now].next[x],p++; else return 0; } return t[now].sum; } int main() { while(gets(s)&&strlen(s))Add_tree(); while(gets(s))cout<<find_tree()<<endl; return 0; }