Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <fstream>
- #include <stdio.h>
- #include <cmath>
- #include <algorithm>
- #include <vector>
- #include <string>
- #define F first
- #define S second
- using namespace std;
- vector <string> ans;
- struct node
- {
- node *p;
- node *nxt[94];
- int ind;
- node *lnk;
- char c;
- bool listt;
- node()
- {
- lnk = p = NULL;
- listt = 0;
- for (int i = 0; i < 94; i++)
- nxt[i] = NULL;
- ind = -1;
- c = 0;
- }
- node(node *_p, char _c, int _ind)
- {
- p = _p;
- c = _c;
- ind = _ind;
- lnk = NULL;
- listt = 0;
- for (int i = 0; i < 94; i++)
- nxt[i] = NULL;
- }
- };
- node *root;
- void add_word(const string &s, int new_ind)
- {
- node *inode = root;
- for (int i = 0; i < s.size(); i++)
- {
- if (inode->nxt[s[i] - ' '] == NULL)
- inode->nxt[s[i] - ' '] = new node(inode, s[i] - ' ', -1);
- inode = inode->nxt[s[i] - ' '];
- }
- inode->ind = new_ind;
- inode->listt = 1;
- }
- void build()
- {
- node *inode, *w;
- vector <node*> q;
- q.push_back(root);
- for (int i = 0; i < q.size(); i++)
- {
- inode = q[i];
- for (int j = 0; j < 94; j++)
- if (inode->nxt[j] != NULL)
- q.push_back(inode->nxt[j]);
- if (inode == root)
- continue;
- if (inode->p == root)
- {
- inode->lnk = root;
- continue;
- }
- w = inode->p;
- w = w->lnk;
- while (w != NULL && w->nxt[inode->c] == NULL)
- w = w->lnk;
- //tree[w].next[tree[v].c]
- inode->lnk = w ->nxt[inode->c] == NULL ? root : w->nxt[inode->c];
- if (inode->ind == -1)
- inode->ind = inode->lnk->ind;
- if (inode->listt == 0)
- inode->listt = inode->lnk->listt;
- }
- }
- node *go(node *inode, char c)
- {
- while (inode != NULL && inode->nxt[c] == NULL)
- inode = inode->lnk;
- return inode == NULL ? root : inode->nxt[c];
- }
- void bfs()
- {
- node *inode;
- vector <node*> q;
- q.push_back(root);
- for (int i = 0; i < q.size(); i++)
- {
- inode = q[i];
- if (inode->lnk->listt)
- inode->listt = 1;
- for (int j = 0; j < 94; j++)
- if (inode->nxt[j] != NULL)
- q.push_back(inode->nxt[j]);
- }
- }
- bool find_word(string &s)
- {
- node *inode = root;
- for (int i = 0; i < s.size(); i++)
- {
- inode = go(inode, s[i] - ' ');
- if (inode->listt)
- {
- return true;
- }
- }
- return false;
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- //cin.tie(0);
- //cout.tie(0);
- //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
- //freopen("console.in", "r", stdin);freopen("console.out", "w", stdout);
- string s;
- int k;
- cin >> k;
- root = new node(NULL, NULL, -1);
- for (int i = 0; i < k; i++)
- {
- cin >> s;
- add_word(s, i);
- }
- build();
- bfs();
- while (getline(cin, s))
- {
- if (find_word(s))
- cout << s << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement