子串查询

题目描述
给出一个长度为n的字符串s和q个查询。对于每一个查询，会输入一个字符串t，你需要判断这个字符串t是不是s的子串。子串的定义就是存在任意下标a<b<c<d<e，那么”s[a]s[b]s[c]s[d]s[e]”就构成s的一个子串。如”abc”的子串有”a”、”b”、”c”、”ab”、”ac”、”bc”、”abc”。
输入描述:
第一行两个数n，q。1<=n，q<=1e5。

第二行一个长度为n的字符串s,所有字符都为小写拉丁字符。

接下来q行每行一个字符串t。1<=|t|<=50。
输出描述:
对于每个查询，如果t是s的字串，输出”YES”,否则输出”NO”。每个答案占一行。
示例1
输入
复制
8 4
ababcbaa
abac
accb
aaaa
abcba
输出
复制
YES
NO
YES
YES

建立字母前缀和，然后二分第一次的位置即可。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,q,cnt[N][30],num[30];
char str[N],op[50];
int bsearch(int l,int r,char x,int k){
	while(l<r){
		int mid=l+r+1>>1;
		if(cnt[mid][x-'a']>=k)	l=mid;
		else	r=mid-1;
	}
	return l;
}
signed main(){
	scanf("%d %d %s",&n,&q,str+1);
	for(int i=n;i>=0;i--){
		for(int j=0;j<26;j++)	cnt[i][j]=num[j];//每个字母后的每个字母个数 
		if(i)	num[str[i]-'a']++;
	}
	while(q--){
		scanf("%s",op+1);	int flag=0;	int len=strlen(op+1);	int x=0;
		for(int i=1;i<=len;i++){
			if(!cnt[x][op[i]-'a']){
				flag++;	break;
			}
			x=bsearch(x,n,op[i],cnt[x][op[i]-'a'])+1;
		}
		puts(flag?"NO":"YES");
	} 
	return 0;
}