/* 开始想耍小聪明 直接map搞 代码短 好理解 空间够 恩 很好 就是 map慢死了 T了 */ #include<iostream> #include<cstdio> #include<cstring> #include<map> using namespace std; int n,m,ans; string s,si; map<string,int>t; int main() { cin>>n; while(n--) { map<string,int>f; cin>>s;int l=s.length(); for(int i=0;i<l;i++) for(int j=i;j<l;j++) { si.clear(); for(int k=i;k<=j;k++)si=si+s[k]; if(!f[si])t[si]++,f[si]=1; } } cin>>m; while(m--) { cin>>s; cout<<t[s]<<endl; } return 0; }
/* 还是老老实实写字典树 这里不需要保证是前缀 只要有就可以 所以对于一个单词 我们把他所有的后缀加到字典树里 注意特殊的 abab这样的 如果按上面说的 会加两遍 ab 所以每个节点我们再维护一个last 表示这个小单词上次是在那个单词里出现 这样就ok了 */ #include<iostream> #include<cstdio> #include<cstring> #include<map> #define maxn 1000010 using namespace std; int n,m,topt; char s[25]; struct node { int next[26],sum,last; }t[maxn]; void Add_tree(int st,int p) { int now=0,l=strlen(s); for(int i=st;i<l;i++) { int x=s[i]-'a'; if(t[now].next[x])now=t[now].next[x]; else { topt++;t[now].next[x]=topt;now=topt; } if(t[now].last!=p)t[now].sum++; t[now].last=p; } } int find_tree() { int now=0,p=0,l=strlen(s); while(p<=l-1) { int x=s[p]-'a'; if(t[now].next[x]) { p++;now=t[now].next[x]; } else return 0; } return t[now].sum; } int main() { scanf("%d",&n); for(int k=1;k<=n;k++) { scanf("%s",s);int l=strlen(s); for(int i=0;i<l;i++) Add_tree(i,k); } scanf("%d",&m); for(int k=1;k<=m;k++) { scanf("%s",s); printf("%d ",find_tree()); } return 0; }