记录编号	554616	评测结果	AAAAA
题目名称	前缀统计	最终得分	100
用户昵称	Oasiz	是否通过	通过
代码语言	C++	运行时间	0.299 s
提交时间	2020-09-16 20:11:37	内存使用	69.99 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,M=5e5+5,W=26;
int trie[N][W],p[N],tot;
string s;
int n,m;
void inn(string k){
	int t=0;
	for(int i=0; k[i]; i++) {
		if(!trie[t][k[i]-'a']){
			trie[t][k[i]-'a']=++tot;
		}
		t=trie[t][k[i]-'a'];
	}
	p[t]++;
}
int FI(string k) {
	int t=0,ans=0;
	for(int i=0; k[i]; i++) {
		if(!trie[t][k[i]-'a']){
			break;
		}
		t=trie[t][k[i]-'a'];
		ans+=p[t];
	}
	return ans;
}
int main() {
	freopen("prefixcal.in","r",stdin);
	freopen("prefixcal.out","w",stdout);
	cin>>n>>m;
	for(int i=0; i<n; i++) {
		cin>>s;
		inn(s);
	}
	for(int i=0; i<m; i++) {
		cin>>s;
		cout<<FI(s)<<endl;
	}
	return 0;
}