记录编号	559311	评测结果	AAAAA
题目名称	前缀统计	最终得分	100
用户昵称	增强型图元文件	是否通过	通过
代码语言	C++	运行时间	0.647 s
提交时间	2021-03-01 20:02:57	内存使用	97.08 MiB

#include <bits/stdc++.h>
#define SIZE 1145141
using namespace std;
int trie[SIZE][26]={0},tot=1;
int cnt[SIZE]={0};
void insert(string x){
	int len=x.size(),p=1;
	for(int k=0;k<len;k++){
		int ch=x[k]-'a';
		if(!trie[p][ch]){
			trie[p][ch]=++tot;
		}
		p=trie[p][ch];
	}
	cnt[p]++;
} 
int search(string x){
	int len =x.size(),p=1;
	int res=0;
	for(int k=0;k<len;k++){
		p=trie[p][x[k]-'a'];
		res+=cnt[p];
		if(p==0)return res;
	}
	return res;
}
int main(int argc, char** argv) {
	freopen("prefixcal.in","r",stdin);
	freopen("prefixcal.out","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string t;
		cin>>t;
		insert(t);
	}
	for(int i=1;i<=m;i++){
		string t;
		cin>>t;
		cout<<search(t)<<endl;
	}
	return 0;
}