比赛 |
20140425 |
评测结果 |
AAAAAAAAAAAAAA |
题目名称 |
子序列 |
最终得分 |
100 |
用户昵称 |
隨風巽 |
运行时间 |
0.062 s |
代码语言 |
C++ |
内存使用 |
0.41 MiB |
提交时间 |
2014-04-25 11:53:19 |
显示代码纯文本
- #include<iostream>
- #include<cstdio>
- #include<vector>
- #include<cstring>
- #include<algorithm>
- #include<cstdlib>
- using namespace std;
- char A[100000+10],B[50+10];
- vector<int>ch[28];//ch[i]表示字母i在字符串A中依次出现的位置
- int M,l,la;
- int query(int num,int pos)
- {
- int l=0,r=ch[num].size()-1,mid,ans=-1;
- while(l<=r)
- {
- mid=(l+r)>>1;
- if(ch[num][mid]>pos)r=(ans=mid)-1;
- else l=mid+1;
- }
- return ans;
- }
- int main()
- {
- freopen("subsequence.in","r",stdin);
- freopen("subsequence.out","w",stdout);
- int i,j,pos;
- scanf("%s",A);
- la=strlen(A);
- for(i=0;i<la;i++)
- ch[A[i]-'a'].push_back(i);
- scanf("%d",&M);
- for(i=1;i<=M;i++)
- {
- scanf("\n%s",B);
- l=strlen(B);
- pos=-1; /////
- for(j=0;j<l;j++)
- {
- pos=query(B[j]-'a',pos);
- if(pos==-1){cout<<"No"<<endl;break;}
- else pos=ch[B[j]-'a'][pos];
- }
- if(j==l)cout<<"Yes"<<endl;
- }
- return 0;
- }