比赛 |
防止浮躁的小练习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;
}