signed

QiShunwang

“诚信为本、客户至上”

newcoder 暗号I (hashmap 二分

2021/3/21 11:01:17   来源:

暗号1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
int vis[30];
unordered_map<string ,int>id;
vector<int>e[1000009];
string func(string s){
	memset(vis,-1,sizeof(vis));
	int len=s.size();
	int tot=-1;
	for(int i=0;i<len;i++){
		if(vis[s[i]-'a']==-1)vis[s[i]-'a']=++tot;//存储为不同的字母用于存储 单纯++会出现aa而不是ab  
		s[i]=vis[s[i]-'a']+'a';//aa 的第二个a直接存储 
	}
	return s;
}

int tot=0;
int main() {
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		s=func(s);
		if(!id[s])id[s]=++tot;
		e[id[s]].push_back(i);//二维存储下标 
	}
	while(q--){
		string s;
		int l,r;
		cin>>s>>l>>r;
		s=func(s);
		if(!id[s]){
			cout<<0<<endl;
		}//确定有则二分查找下标 
		else cout<<upper_bound(e[id[s]].begin(),e[id[s]].end(),r) - lower_bound(e[id[s]].begin(),e[id[s]].end(),l)<<endl;
	}
	return 0;
}