fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll int
  4. #define mo 1000000007
  5.  
  6. map<ll,ll>trie[26][26];
  7. ll sz=0;
  8. char p[500005],c[500005];
  9. void ins(string s,ll root)
  10. {
  11. ll st=0;
  12. for(ll i=0;i<s.size();i++)
  13. {
  14. ll cur=s[i]-65;
  15. if(trie[root][cur][st]==0)
  16. trie[root][cur][st]=++sz;
  17. st=trie[root][cur][st];
  18. }
  19. }
  20. ll ch(string s,ll root)
  21. {
  22. ll st=0;
  23. for(ll i=0;i<s.size();i++)
  24. {
  25. ll cur=s[i]-65;
  26. if(trie[root][cur][st]==0)
  27. return 0;
  28. st=trie[root][cur][st];
  29. }
  30. return 1;
  31. }
  32. int main()
  33. {
  34. ll i,j,k,n,m,t;
  35. scanf("%d %d",&n,&t);
  36. scanf("%s",p);
  37. map<char,char>vk;
  38. for(i=0;i<n;i++)
  39. {
  40. char now=(char)(i+65);
  41. vk[now]=p[i];
  42. }
  43. ll f=0;
  44. while(t--)
  45. {
  46. ll tp;
  47. scanf("%d",&tp);
  48. if(tp==1)
  49. {
  50. scanf("%s",c);
  51. ins(c,0);
  52. string pre=c;
  53. for(i=1;i<n;i++)
  54. {
  55. string now=pre;
  56. for(j=0;j<pre.size();j++)
  57. {
  58. now[j]=vk[now[j]];
  59. }
  60. ins(now,i);
  61. pre=now;
  62. }
  63. }
  64. else if(tp==2)
  65. {
  66. f+=1;
  67. f%=n;
  68. }
  69. else
  70. {
  71. scanf("%s",c);
  72. if(ch(c,f))
  73. {
  74. printf("YES\n");
  75. }
  76. else printf("NO\n");
  77. }
  78. }
  79.  
  80. }
  81.  
Success #stdin #stdout 0s 4356KB
stdin
Standard input is empty
stdout
Standard output is empty