M. Subsequence 2019南昌邀请赛网络赛

M. Subsequence

The Preliminary Contest for ICPC China Nanchang National Invitational and International Silk-Road Programming Contest

这个运行超时到自闭呀。3001m一直超时，最后我吧cin换成了scanf 把字符串换成字符数组过了。这个事项告诉我，比赛的时候不要偷懒用cin或者加上一句消除cin比scanf慢的语句。

题意：题意很简单，和紫书上一题非常像，就是这个数据量特别特别大。

思路：加油优化，预处理。用一个数组记录母串26个字母所在的位置有哪些。然后再查询的时候，直接找子串的这个字母再母串中还有没有。有好几种情况都是没有了，不用再往下找了，详情可以看代码。主要是根据子层前一个字母再母串中的位置tmp，判断现在在母串中关于该字母有没有在tmp之后的。然后再预处理数组中找的时候要二分一下。

总结就是，各种操作，瞎弄弄。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1e5+10;
char s[maxn],str[maxn];
int cnt[26];
int st[26][maxn];
int main(){
	
	int n;
	scanf("%s",&str);
	scanf("%d",&n);
	int len=strlen(str);
	memset(cnt,0,sizeof(cnt));
	for(int i=0;i<len;i++){
		st[str[i]-'a'][cnt[str[i]-'a']]=i;
		cnt[str[i]-'a']++;
	}
	int ip[26];
	for(int k=0;k<n;k++){
		scanf("%s",&s);
		memset(ip,0,sizeof(ip));
		int lens=strlen(s);
		if(lens>len){
			printf("NO\n");
			continue;
		}
		int flag=0,tmp=-1;
		for(int i=0;i<lens;i++){
			int u=s[i]-'a';
			if(ip[u]>=cnt[u]||cnt[u]<=0){
				flag=1;
				break;
			}
			if(tmp==-1){
				tmp=st[u][ip[u]++];
			}
			else{
				if(st[u][cnt[u]-1]<tmp){
					flag=1;
					break;//肯定没有了 
				}
				int l=ip[u],r=cnt[u];//zhe 
				while(l<=r){//二分查找位置 
					int mid=(l+r)/2; 
					if(tmp>st[u][mid]) l=mid+1;
					else r=mid-1;
				} 
				ip[u]=l;
				//while(tmp>st[u][ip[u]]) ip[u]++;//这里可以优化 
				tmp=st[u][ip[u]++];
			}
			
		}
		if(!flag) printf("YES\n");
		else printf("NO\n");	
	}
	
	return 0;
}