比赛 |
20140425 |
评测结果 |
AAAAAAAAAAAAAA |
题目名称 |
子序列 |
最终得分 |
100 |
用户昵称 |
cstdio |
运行时间 |
0.656 s |
代码语言 |
C++ |
内存使用 |
61.74 MiB |
提交时间 |
2014-04-25 10:37:30 |
显示代码纯文本
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<fstream>
- #include<vector>
- using namespace std;
- ifstream fin("subsequence.in");
- ofstream fout("subsequence.out");
- 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;
- if(test(B)) fout<<"Yes"<<endl;
- else fout<<"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);
- fin>>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();
- fin.close();
- fout.close();
- return 0;
- }