比赛 20140425 评测结果 AAAAAAAAAAAAAA
题目名称 子序列 最终得分 100
用户昵称 cstdio 运行时间 0.656 s
代码语言 C++ 内存使用 61.74 MiB
提交时间 2014-04-25 10:37:30
显示代码纯文本
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<fstream>
  6. #include<vector>
  7. using namespace std;
  8. ifstream fin("subsequence.in");
  9. ofstream fout("subsequence.out");
  10. const int SIZELA=100010,SIZEM=10001,SIZELB=51;
  11. string A;
  12. int L;
  13. int M;
  14. int next[SIZELA][26]={0};
  15. class NODE{
  16. public:
  17. int pos;//匹配位置
  18. int son[26];
  19. void clear(void){
  20. pos=0;
  21. memset(son,-1,sizeof(son));
  22. }
  23. NODE(){clear();}
  24. };
  25. NODE trie[SIZEM*50+10];
  26. int tot=0;
  27. bool test(string &s){
  28. int rt=0;
  29. for(int i=0;i<s.size();i++){
  30. NODE &now=trie[rt];
  31. if(next[now.pos][s[i]-'a']==-1) return false;
  32. if(now.son[s[i]-'a']==-1){
  33. tot++;
  34. trie[tot].pos=next[now.pos][s[i]-'a'];
  35. now.son[s[i]-'a']=tot;
  36. }
  37. rt=now.son[s[i]-'a'];
  38. }
  39. return true;
  40. }
  41. void work(void){
  42. string B;
  43. for(int i=1;i<=M;i++){
  44. fin>>B;
  45. if(test(B)) fout<<"Yes"<<endl;
  46. else fout<<"No"<<endl;
  47. }
  48. }
  49. void init(void){
  50. memset(next,-1,sizeof(next));
  51. int now[26]={0};
  52. memset(now,-1,sizeof(now));
  53. for(int i=L;i>=1;i--){
  54. memcpy(next[i],now,sizeof(now));
  55. now[A[i]-'a']=i;
  56. }
  57. memcpy(next[0],now,sizeof(now));
  58. }
  59. int main(){
  60. //freopen("subsequence.in","r",stdin);
  61. //freopen("subsequence.out","w",stdout);
  62. fin>>A>>M;
  63. //cout<<A<<endl;
  64. L=A.size();
  65. //for(int i=0;i<=10;i++) cout<<A[i];cout<<endl;
  66. A="0"+A;
  67. //cout<<A<<" "<<L<<endl;
  68. //cout<<A[2]<<endl;
  69. init();
  70. work();
  71. fin.close();
  72. fout.close();
  73. return 0;
  74. }