Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #pragma comment(linker, "/STACK:256000000")
- #include <bits/stdc++.h>
- #ifdef _DEBUG
- #include "optimization.h"
- #endif
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef pair<ll, ll> pll;
- typedef pair<int, int> pii;
- #define TASK "tree"
- #define X first
- #define Y second
- #define inb push_back
- #define y1 dfsdfsd
- class Aho
- {
- public:
- vector<vector<int>> go;
- vector<bool> term;
- vector<int> suf;
- Aho()
- {
- go.inb(vector<int>(100)), go.inb(vector<int>(100)), term.inb(0), term.inb(0), suf.inb(0), suf.inb(0);
- }
- void add(char *&s, int i)
- {
- int v = 1;
- int x = strlen(s);
- for (int i = 0; i < x; ++i)
- {
- int c = s[i] - ' ';
- if (!go[v][c]) go[v][c] = go.size(), go.inb(vector<int>(100)), term.inb(0), suf.inb(0);
- v = go[v][c];
- }
- term[v] = 1;
- }
- void bfs()
- {
- queue<int> q;
- q.push(1);
- while (q.size())
- {
- int v = q.front();
- q.pop();
- for (int c = 0; c < 100; ++c)
- {
- int u = (v == 1 ? 1 : go[suf[v]][c]);
- if (go[v][c])
- {
- suf[go[v][c]] = u;
- q.push(go[v][c]);
- }
- else
- go[v][c] = u;
- }
- term[v] = max(term[v], term[suf[v]]);
- }
- }
- bool get(char *&s)
- {
- int x = strlen(s);
- int v = 1;
- for (int i = 0; i < x; ++i)
- {
- int c = s[i] - ' ';
- if (!go[v][c]) return 0;
- v = go[v][c];
- if (term[v]) return 1;
- }
- return 0;
- }
- };
- int main()
- {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
- #else
- //freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
- //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
- #endif
- char *a, *s;
- a = new char[100];
- s = new char[300];
- int m;
- m = readInt();
- Aho d;
- for (int i = 0; i < m; ++i)
- {
- readLine(a);
- d.add(a, i);
- }
- d.bfs();
- while (!isEof())
- {
- readLine(s);
- if (d.get(s)) writeWord(s), writeChar('\n');
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement