比赛 20140425 评测结果 AAAAAAAAAAAAAA
题目名称 子序列 最终得分 100
用户昵称 隨風巽 运行时间 0.062 s
代码语言 C++ 内存使用 0.41 MiB
提交时间 2014-04-25 11:53:19
显示代码纯文本
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<vector>
  4. #include<cstring>
  5. #include<algorithm>
  6. #include<cstdlib>
  7. using namespace std;
  8. char A[100000+10],B[50+10];
  9. vector<int>ch[28];//ch[i]表示字母i在字符串A中依次出现的位置
  10. int M,l,la;
  11. int query(int num,int pos)
  12. {
  13. int l=0,r=ch[num].size()-1,mid,ans=-1;
  14. while(l<=r)
  15. {
  16. mid=(l+r)>>1;
  17. if(ch[num][mid]>pos)r=(ans=mid)-1;
  18. else l=mid+1;
  19. }
  20. return ans;
  21. }
  22. int main()
  23. {
  24. freopen("subsequence.in","r",stdin);
  25. freopen("subsequence.out","w",stdout);
  26. int i,j,pos;
  27. scanf("%s",A);
  28. la=strlen(A);
  29. for(i=0;i<la;i++)
  30. ch[A[i]-'a'].push_back(i);
  31. scanf("%d",&M);
  32. for(i=1;i<=M;i++)
  33. {
  34. scanf("\n%s",B);
  35. l=strlen(B);
  36. pos=-1; /////
  37. for(j=0;j<l;j++)
  38. {
  39. pos=query(B[j]-'a',pos);
  40. if(pos==-1){cout<<"No"<<endl;break;}
  41. else pos=ch[B[j]-'a'][pos];
  42. }
  43. if(j==l)cout<<"Yes"<<endl;
  44. }
  45. return 0;
  46. }