记录编号	589868	评测结果	AAAAAAAAAA
题目名称	单词默写	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	2.202 s
提交时间	2024-07-08 14:32:58	内存使用	73.02 MiB

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000010
#define MAXM 100010 
struct node{
    int num,cnt,ans;
    string s;
}qs[MAXM],wd[MAXM];
bool cmp(node a,node b){
    return a.cnt>b.cnt;
}
bool cmp2(node a,node b){
    return a.num<b.num;
}
int n,m,idx=1,res=1;
int s[MAXN][27],ans[MAXN];
void build(string p){
    int len=p.length(),now=1;
    for(int i=1;i<=len;i++){
        int f=p[i-1]-'a';
//        cout<<"now: "<<now<<" ans:"<<ans[now]<<endl;
        if(s[now][f]){
            now=s[now][f];
        }else{
            s[now][f]=++idx;
            now=idx;
        }
        ans[now]++;
    }
}
int qs_(string p){
    int len=p.length(),now=1;
    for(int i=1;i<=len;i++){
        int f=p[i-1]-'a';
//        cout<<now<<" "<<f<<endl;  
        if(s[now][f]){
            now=s[now][f];
        }else{
            return 0;
        } 
    }
    return ans[now];
} 
int main(){
    freopen("engzam.in","r",stdin);
    freopen("engzam.out","w",stdout);
    scanf("%d%d",&n,&m);//cin>>n>>m;
    for(int i=1;i<=n;i++){
//        scanf("%d%d",&wd[i].s,&wd[i].cnt);
        cin>>wd[i].s>>wd[i].cnt;
    }
    for(int i=1;i<=m;i++){
//        scanf("%d%d",&qs[i].s,&qs[i].cnt);
        cin>>qs[i].s>>qs[i].cnt;
        qs[i].num=i;
    }
    sort(wd+1,wd+1+n,cmp);
    sort(qs+1,qs+1+m,cmp);
    for(int i=1;i<=m;i++){
//        cout<<qs[i].num<<endl;
        while(res<=n){
            if(wd[res].cnt>=qs[i].cnt)build(wd[res++].s);
            else break;
        }
//        cout<<"res:"<<res<<endl;
        qs[i].ans=qs_(qs[i].s);
    }
    sort(qs+1,qs+1+m,cmp2);
    for(int i=1;i<=m;i++){//printf("%d\n",qs[i].ans);
        cout<<qs[i].ans<<endl;
    }
//    return cerr<<clock()<<"ms"<<endl,0;
    return 0;
}