SHOW:
|
|
- or go back to the newest paste.
| 1 | #include <bits/stdc++.h> | |
| 2 | ||
| 3 | using namespace std; | |
| 4 | ||
| 5 | struct node {
| |
| 6 | node* letters[26]; | |
| 7 | vector<int> has_ans; | |
| 8 | node* suf_mail, *pred; | |
| 9 | int last_symb; | |
| 10 | node() {
| |
| 11 | fill(letters, letters + 26, nullptr); | |
| 12 | suf_mail = nullptr; | |
| 13 | pred = nullptr; | |
| 14 | has_ans.clear(); | |
| 15 | last_symb = 1; | |
| 16 | } | |
| 17 | }; | |
| 18 | ||
| 19 | void make_bor(node * now, string& s, int ind, int j) {
| |
| 20 | if (ind == (int) s.size()) {
| |
| 21 | now->has_ans.push_back(j); | |
| 22 | return; | |
| 23 | } | |
| 24 | if (now->letters[s[ind] - 'a'] == nullptr) {
| |
| 25 | node* new_node = new node(); | |
| 26 | new_node->last_symb = s[ind] - 'a'; | |
| 27 | new_node->pred = now; | |
| 28 | now->letters[s[ind] - 'a'] = new_node; | |
| 29 | } | |
| 30 | make_bor(now->letters[s[ind] - 'a'], s, ind + 1, j); | |
| 31 | } | |
| 32 | ||
| 33 | set<node*> used; | |
| 34 | queue<node*> que; | |
| 35 | vector<int> ans; | |
| 36 | ||
| 37 | void go(node * now, string& s, int ind) {
| |
| 38 | used.insert(now); | |
| 39 | if (ind == (int) s.size()) {
| |
| 40 | return; | |
| 41 | } | |
| 42 | go(now->letters[s[ind] - 'a'], s, ind + 1); | |
| 43 | } | |
| 44 | ||
| 45 | int main() {
| |
| 46 | ios_base::sync_with_stdio(0); | |
| 47 | cin.tie(0); | |
| 48 | node * root = new node(); | |
| 49 | root->pred = root; | |
| 50 | int n; | |
| 51 | cin >> n; | |
| 52 | for (int i = 0; i < n; i++) {
| |
| 53 | string s1; | |
| 54 | cin >> s1; | |
| 55 | make_bor(root, s1, 0, i + 1); | |
| 56 | } | |
| 57 | root->suf_mail = root; | |
| 58 | queue<node*> bfs; | |
| 59 | bfs.push(root); | |
| 60 | while (!bfs.empty()) {
| |
| 61 | node * next = bfs.front(); | |
| 62 | bfs.pop(); | |
| 63 | if (next == root) {
| |
| 64 | for (int i = 0; i < 26; i++) {
| |
| 65 | if (next->letters[i] != nullptr) {
| |
| 66 | bfs.push(next->letters[i]); | |
| 67 | } else {
| |
| 68 | next->letters[i] = root; | |
| 69 | } | |
| 70 | } | |
| 71 | continue; | |
| 72 | } | |
| 73 | node * now = next->pred; | |
| 74 | if (now == root) {
| |
| 75 | next->suf_mail = now; | |
| 76 | for (int i = 0; i < 26; i++) {
| |
| 77 | if (next->letters[i] != nullptr) {
| |
| 78 | bfs.push(next->letters[i]); | |
| 79 | } else {
| |
| 80 | next->letters[i] = next->suf_mail->letters[i]; | |
| 81 | } | |
| 82 | } | |
| 83 | continue; | |
| 84 | } | |
| 85 | int next_char = next->last_symb; | |
| 86 | next->suf_mail = next->pred->suf_mail->letters[next_char]; | |
| 87 | for (int i = 0; i < 26; i++) {
| |
| 88 | if (next->letters[i] != nullptr) {
| |
| 89 | bfs.push(next->letters[i]); | |
| 90 | } else {
| |
| 91 | next->letters[i] = next->suf_mail->letters[i]; | |
| 92 | } | |
| 93 | } | |
| 94 | } | |
| 95 | ans.resize(n); | |
| 96 | string s; | |
| 97 | cin >> s; | |
| 98 | go(root, s, 0); | |
| 99 | for (auto& i : used) {
| |
| 100 | que.push(i); | |
| 101 | } | |
| 102 | while (!que.empty()) {
| |
| 103 | node * now = que.front(); | |
| 104 | que.pop(); | |
| 105 | if (now->has_ans.size() != 0) {
| |
| 106 | for (unsigned int i = 0; i < now->has_ans.size(); i++) {
| |
| 107 | ans[now->has_ans[i] - 1] = 1; | |
| 108 | } | |
| 109 | } | |
| 110 | if (used.count(now->suf_mail) == 0) {
| |
| 111 | used.insert(now->suf_mail); | |
| 112 | que.push(now->suf_mail); | |
| 113 | } | |
| 114 | } | |
| 115 | for (int j = 0; j < n; ++j) {
| |
| 116 | if (ans[j] == 1) {
| |
| 117 | cout << "YES" << endl; | |
| 118 | } else {
| |
| 119 | cout << "NO" << endl; | |
| 120 | } | |
| 121 | } | |
| 122 | return 0; | |
| 123 | } |
