Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <set>
- #include <map>
- using namespace std;
- vector<vector<int>> trie(1000000 + 100, vector<int>(27, -1));
- int m = 1;
- int root = 0;
- set<int> T;
- vector<pair<int, int>> p(1000000 + 100);
- vector<int> suf_link(1000000 + 100);
- map<int, string> term;
- vector<bool> used(1000000 + 100, false);
- void insert(string &s) {
- auto v = root;
- for (auto c : s) {
- if (trie[v][c - 'a'] == -1) {
- trie[v][c - 'a'] = m++;
- p[m - 1] = {v, c};
- }
- v = trie[v][c - 'a'];
- }
- term[v] = s;
- T.insert(v);
- }
- void make_suffix_links() {
- suf_link[root] = root;
- queue<int> q;
- for (int i = 0; i < 27; i++) {
- if (trie[root][i] != -1) {
- for (int j = 0; j < 27; j++) if (trie[trie[root][i]][j] != -1) q.push(trie[trie[root][i]][j]);
- suf_link[trie[root][i]] = root;
- }
- }
- while (!q.empty()) {
- auto t = q.front();
- q.pop();
- auto pp = p[t];
- auto next = suf_link[pp.first];
- while (next != root && trie[next][pp.second - 'a'] == -1) {
- next = suf_link[next];
- }
- if (trie[next][pp.second - 'a'] == -1) suf_link[t] = root;
- else suf_link[t] = trie[next][pp.second - 'a'];
- for (int i = 0; i < 27; i++) {
- if (trie[t][i] != -1)
- q.push(trie[t][i]);
- }
- }
- }
- int main() {
- freopen("search4.in", "r", stdin);
- freopen("search4.out", "w", stdout);
- int n;
- vector<string> strings;
- cin >> n;
- for (int i = 0; i < n; i++) {
- string s;
- cin >> s;
- insert(s);
- strings.emplace_back(s);
- }
- make_suffix_links();
- string t;
- cin >> t;
- int cur = root;
- set<int> ans;
- for (auto &ch : t) {
- while (trie[cur][ch - 'a'] == -1 && cur != root) {
- cur = suf_link[cur];
- }
- if (trie[cur][ch - 'a'] != -1)
- cur = trie[cur][ch - 'a'];
- auto go = cur;
- while (go != root && !used[go]) {
- used[go] = true;
- if (T.count(go) > 0) {
- ans.insert(go);
- }
- go = suf_link[go];
- }
- }
- set<string> res;
- for (auto &cc : ans) {
- res.insert(term[cc]);
- }
- for (auto &s : strings) {
- (res.count(s) == 0 ? cout << "NO\n" << endl : cout << "YES\n" );
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement