Advertisement
Guest User

Untitled

a guest
Feb 19th, 2020
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string arr[1000000];
  4. struct vertex{
  5.     bool is=false;
  6.     int p=-1;
  7.     char pch;
  8.     int link=-1;
  9.     int go[27];
  10.     int next[27];
  11.     string word;
  12.     vertex(int p=-1, char ch='$') :p(p), pch(ch){
  13.         fill(begin(next), end(next), -1);
  14.         fill(begin(go), end(go), -1);
  15.     }
  16. };
  17. vector<vertex> vv;
  18. void add_string(string const& s){
  19.     int v=0;
  20.     for(char ch:s){
  21.         int c=ch-'a';
  22.         if(vv[v].next[c]==-1){
  23.             vv[v].next[c]=vv.size();
  24.             vv.emplace_back(v, ch);
  25.         }
  26.         v=vv[v].next[c];
  27.     }
  28.     vv[v].is=true;
  29.     vv[v].word=s;
  30.     cout<<vv[v].word;
  31. }
  32. int go(int v, char ch);
  33. int link(int v){
  34.     if(vv[v].link==-1){
  35.         if(v==0 || vv[v].p==0)
  36.             vv[v].link=0;
  37.         else
  38.             vv[v].link=go(link(vv[v].p), vv[v].pch);
  39.     }
  40.     return vv[v].link;
  41. }
  42. int go(int v, char ch){
  43.     int c=ch-'a';
  44.     if(vv[v].go[c]==-1){
  45.         if(vv[v].next[c]!=-1)
  46.             vv[v].go[c]=vv[v].next[c];
  47.         else
  48.             vv[v].go[c]= v==0?0:go(link(v), ch);
  49.     }
  50.     return vv[v].go[c];
  51. }
  52. vector<int> visited;
  53. set<string> ss;
  54. void addsolution(int second){
  55.     visited[second]=1;
  56.     int k=link(second);
  57.     if(visited[k]==0)
  58.         addsolution(k);
  59.     if(vv[second].is)
  60.         ss.insert(arr[second]);
  61. }
  62. int main(){
  63. int n;
  64. cin>>n;
  65. for(int i=0; i<n; i++){
  66.     cin>>arr[i];
  67.     add_string(arr[i]);
  68. }
  69. visited.assign(n, 0);
  70. string hay;
  71. cin>>hay;
  72. int u;
  73. for(auto x:hay){
  74.     u=go(u, x);
  75.     addsolution(u);
  76. }
  77. for(int i=0; i<n; i++){
  78.     if(ss.find(arr[i])!=ss.end())
  79.         cout<<"YES";
  80.     else
  81.         cout<<"NO";
  82. }
  83. return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement