记录编号	176316	评测结果	AAAAATTTTT
题目名称	单词默写	最终得分	50
用户昵称	一個人的雨	是否通过	未通过
代码语言	C++	运行时间	5.004 s
提交时间	2015-08-08 16:37:14	内存使用	116.86 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
#define idx(x) x - 'a' + 1;
const int MAXN=1e6+10000;
struct Tire {
    int next[28];
    int val;
    int flag;
}tree[MAXN];
char str[MAXN];
int nxt=1,n,m,cnt,S[100],tim=1;

void work(int,char *,int,int);

int add(){
    memset(&tree[nxt],0,sizeof(Tire));
    return nxt++;
}

void Insert(char *s,int x){
	int rt=0,l=strlen(s);
	for (int i=0;i<l;++i){
		int num=idx(s[i]);
		if (!tree[rt].next[num]) tree[rt].next[num]=add();
		rt=tree[rt].next[num];
	}
	tree[rt].val+=x;
}

bool Find(char *s,int x){
	int rt=0,l=strlen(s);
	for (int i=0;i<l;++i){
		int num=idx(s[i]);
		if (!tree[rt].next[num]) return false;
		rt=tree[rt].next[num];
	}
	work(rt,s,1,x);
	return 1;
}

void work(int rt,char *s,int num,int x){
	int k;
	for (k=1;k<=26;++k){
		S[num]=k;
		if (tree[rt].val&&tree[rt].flag!=tim&&tree[rt].val>=x) {
			cnt++;
			tree[rt].flag=tim;
		}
		if (tree[rt].next[k]){
			int p=tree[rt].next[k];//千万不要再用rt!!!
			work(p,s,num+1,x);
		}
	}
}

int main(){
	freopen("engzam.in","r",stdin);
	freopen("engzam.out","w",stdout);
	scanf("%d",&n);int x;scanf("%d",&m);
	memset(&tree[0],0,sizeof(Tire));
	for (int i=1;i<=n;++i){
		scanf("%s %d",str,&x);
        Insert(str,x);
	}
	for (int i=1;i<=m;++i){
		scanf("%s %d",str,&x);
		++tim;
		cnt=0; Find(str,x);
		printf("%d\n",cnt);
	}
	return 0;
}