前缀统计

思路

$trie$树模板题。

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=1e5+10;
int z[tt][26];
int cnt[tt];
int idx=0;

void insert(string s){
    int p=0;
    for(int i=0;i<s.size();i++){
        int w=s[i]-'a';
        if(!z[p][w]){
        	idx++;
			z[p][w]=idx;
		}
        p=z[p][w];
    }
    cnt[p]++;
}

int solve(string str){
    int p=0,ans=0;
    for(int i=0;i<str.size();i++){
        int w=str[i]-'a';
        p=z[p][w];
        if(p==0) return ans;
        ans+=cnt[p];
    }
	return ans;
}

int main(){
    int n,m;
    cin >>n>>m;
    string s;
    for(int i=1;i<=n;i++){
    	cin >>s;
    	insert(s);
	}
    for(int i=1;i<=m;i++){
    	cin >>s;
		cout <<solve(s)<<endl;
	}
    return 0;
}