子串查询

链接：https://ac.nowcoder.com/acm/contest/1083/B 来源：牛客网

题目描述：

给出一个长度为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

分析：一个字符串查询一次时间复杂度无疑很高，肯定会超时，增加标志位，每个字母都标出下一个字母的位置，子串查询的时候直接查询下一个字母的下标，省去了遍历的过程，只遍历一次原数组增加标志位

完整代码：

#include<iostream>
#include<vector>
#include<string>
#include <algorithm>
using namespace std;
vector<long long > vec;
string s;
int p,q;
int main(){
	vector<int > vec[27];  //存放标志位
	string str;
	int len;
	cin>>p>>q;
	cin>>s;
	for(int i=0,len=s.length();i<len;i++) vec[s[i]-'a'].push_back(i);
	while(q--){
		cin>>str;
		int flag=0;
		int pos=-1;
		for(int k=0,n=str.length();k<n;k++){
			vector<int>::iterator it =upper_bound(vec[str[k]-'a'].begin(),vec[str[k]-'a'].end(),pos);
			if(it==vec[str[k]-'a'].end()){
				flag=1;
				break;
			}
			pos=*it;
		}
		if(flag)
			cout<<"NO"<<endl;
		else
			cout<<"YES"<<endl;
	}
}