比赛 防止浮躁的小练习v0.7 评测结果 AAAAAAAAAAAAAA
题目名称 子序列 最终得分 100
用户昵称 _Itachi 运行时间 1.091 s
代码语言 C++ 内存使用 57.32 MiB
提交时间 2016-10-27 14:26:20
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<fstream>
#include<vector>
using namespace std;
const int SIZELA=100010,SIZEM=10001,SIZELB=51;
string A;
int L;
int M;
int next[SIZELA][26]={0};
class NODE{
public:
	int pos;//匹配位置
	int son[26];
	void clear(void){
		pos=0;
		memset(son,-1,sizeof(son));
	}
	NODE(){clear();}
};
NODE trie[SIZEM*50+10];
int tot=0;
bool test(string &s){
	int rt=0;
	for(int i=0;i<s.size();i++){
		NODE &now=trie[rt];
		if(next[now.pos][s[i]-'a']==-1) return false;
		if(now.son[s[i]-'a']==-1){
			tot++;
			trie[tot].pos=next[now.pos][s[i]-'a'];
			now.son[s[i]-'a']=tot;
		}
		rt=now.son[s[i]-'a'];
	}
	return true;
}
void work(void){
	string B;
	for(int i=1;i<=M;i++){
		//fin>>B;
		cin>>B;
		if(test(B)) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}
void init(void){
	memset(next,-1,sizeof(next));
	int now[26]={0};
	memset(now,-1,sizeof(now));
	for(int i=L;i>=1;i--){
		memcpy(next[i],now,sizeof(now));
		now[A[i]-'a']=i;
	}
	memcpy(next[0],now,sizeof(now));
}
int main(){
	freopen("subsequence.in","r",stdin);
	freopen("subsequence.out","w",stdout);
	ios::sync_with_stdio(false);
	//fin>>A>>M;
	cin>>A>>M;
	//cout<<A<<endl;
	L=A.size();
	//for(int i=0;i<=10;i++) cout<<A[i];cout<<endl;
	A="0"+A;
	//cout<<A<<" "<<L<<endl;
	//cout<<A[2]<<endl;
	init();
	work();
	return 0;
}