Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- string arr[1000000];
- struct vertex{
- bool is=false;
- int p=-1;
- char pch;
- int link=-1;
- int go[27];
- int next[27];
- string word;
- vertex(int p=-1, char ch='$') :p(p), pch(ch){
- fill(begin(next), end(next), -1);
- fill(begin(go), end(go), -1);
- }
- };
- vector<vertex> vv;
- void add_string(string const& s){
- int v=0;
- for(char ch:s){
- int c=ch-'a';
- if(vv[v].next[c]==-1){
- vv[v].next[c]=vv.size();
- vv.emplace_back(v, ch);
- }
- v=vv[v].next[c];
- }
- vv[v].is=true;
- vv[v].word=s;
- cout<<vv[v].word;
- }
- int go(int v, char ch);
- int link(int v){
- if(vv[v].link==-1){
- if(v==0 || vv[v].p==0)
- vv[v].link=0;
- else
- vv[v].link=go(link(vv[v].p), vv[v].pch);
- }
- return vv[v].link;
- }
- int go(int v, char ch){
- int c=ch-'a';
- if(vv[v].go[c]==-1){
- if(vv[v].next[c]!=-1)
- vv[v].go[c]=vv[v].next[c];
- else
- vv[v].go[c]= v==0?0:go(link(v), ch);
- }
- return vv[v].go[c];
- }
- vector<int> visited;
- set<string> ss;
- void addsolution(int second){
- visited[second]=1;
- int k=link(second);
- if(visited[k]==0)
- addsolution(k);
- if(vv[second].is)
- ss.insert(arr[second]);
- }
- int main(){
- int n;
- cin>>n;
- for(int i=0; i<n; i++){
- cin>>arr[i];
- add_string(arr[i]);
- }
- visited.assign(n, 0);
- string hay;
- cin>>hay;
- int u;
- for(auto x:hay){
- u=go(u, x);
- addsolution(u);
- }
- for(int i=0; i<n; i++){
- if(ss.find(arr[i])!=ss.end())
- cout<<"YES";
- else
- cout<<"NO";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement