牛客 练习 51B
子串查询
https://ac.nowcoder.com/acm/contest/1083/B
题目描述 ：给你一个母串s 让你在给你q个串ss问你是不是s的子串
分析：存储字母的下标大小，在每次二分查找当前字母最小的下标 如果没找到就输出NO
1<=n，q<=1e5。 |ss|<=50
ac代码：
#include<iostream>
#include<map>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
using namespace std;
map<int ,int >vis;
vector<long long > vec;
int main(){
// freopen("1.txt","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0);
vector<int >vec[50];
int n,q;
cin>>n>>q;
string s;
cin>>s;
for(int i=0,sz=s.length();i<sz;i++)vec[s[i]-'a'].push_back(i);
while(q--){
string ss;
cin>>ss;
int pos=-1,flag=0;
for(int i=0,sz=ss.length();i<sz;i++){
vector<int>::iterator it=upper_bound(vec[ss[i]-'a'].begin(),vec[ss[i]-'a'].end(),pos);
if(it==vec[ss[i]-'a'].end()){ flag=1;break;}
pos=*it;
// cout<<pos<<endl;
}
if(flag) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}
投递贝壳找房等公司10个岗位 >
腾讯HR面348人在聊