Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <time.h>
- #include <string.h>
- #include <cstring>
- #include <cmath>
- #include <algorithm>
- #include <queue>
- #include <stack>
- #include <cassert>
- #include <set>
- #include <vector>
- #include <map>
- using namespace std;
- const int N = 1111111;
- const int K = 26;
- struct Node {
- Node* son[K];
- Node* go[K];
- Node* parent;
- Node* suff_link;
- Node* up;
- char char_to_parent;
- bool is_leaf;
- bool was_marked;
- vector <int> leaf_number;
- Node() {
- for(int j = 0; j < K; ++j) {
- son[j] = go[j] = nullptr;
- }
- parent = suff_link = up = nullptr;
- is_leaf = was_marked = false;
- }
- };
- Node* root;
- void add(string s, int number) {
- Node* cur = root;
- for(int i = 0; i < (int) s.size(); ++i) {
- char c = s[i];
- int k = c - 'a';
- if(cur->son[k] == nullptr) {
- cur->son[k] = new Node;
- cur->son[k]->parent = cur;
- cur->son[k]->char_to_parent = c;
- }
- cur = cur->son[k];
- }
- cur->is_leaf = true;
- cur->leaf_number.push_back(number);
- }
- Node* get_link(Node* v, char c);
- Node* get_suff_link(Node* v);
- Node* get_up(Node* v);
- Node* get_link(Node* v, char c) {
- int k = c - 'a';
- if(v->go[k] == nullptr) {
- if(v->son[k] != nullptr) {
- v->go[k] = v->son[k];
- } else
- if(v == root) {
- v->go[k] = root;
- } else {
- v->go[k] = get_link(get_suff_link(v), c);
- }
- }
- return v->go[k];
- }
- Node* get_suff_link(Node* v) {
- if(v->suff_link == nullptr) {
- if(v == root || v->parent == root) {
- v->suff_link = root;
- } else {
- v->suff_link = get_link(get_suff_link(v->parent), v->char_to_parent);
- }
- }
- return v->suff_link;
- }
- Node* get_up(Node* v) {
- if(v->up == nullptr) {
- if(get_suff_link(v)->is_leaf) {
- v->up = get_suff_link(v);
- } else
- if(get_suff_link(v) == root) {
- v->up = root;
- } else {
- v->up = get_up(get_suff_link(v));
- }
- }
- return v->up;
- }
- bool ans[N];
- int main(){
- freopen("dictionary.in", "r", stdin);
- freopen("dictionary.out", "w", stdout);
- string t;
- cin >> t;
- root = new Node;
- int n;
- cin >> n;
- for(int i = 0; i < n; ++i) {
- string s;
- cin >> s;
- add(s, i);
- }
- Node* cur = root;
- for(int i = 0; i < (int) t.size(); ++i) {
- char c = t[i];
- cur = get_link(cur, c);
- Node* temp = cur;
- while(temp != root) {
- if(temp->was_marked) break;
- for(int x : temp->leaf_number) {
- ans[x] = true;
- }
- temp->was_marked = true;
- temp = get_up(temp);
- }
- }
- for(int i = 0; i < n; ++i) {
- cout << (ans[i] ? "Yes\n" : "No\n");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement