Untitled
unknown
plain_text
a year ago
2.1 kB
5
Indexable
#include <ios> #include <iostream> #include <string> #include <vector> static constexpr size_t ALPHABET_SIZE = 26; struct Node { uint32_t length; int link{ -1 }; std::vector<int> to; Node(uint32_t length): length(length), to(ALPHABET_SIZE, -1) {} }; void add(uint32_t ch, std::vector<Node>& nodes) { uint32_t length = nodes.back().length + 1; int node = nodes.size() - 1; uint32_t cur = nodes.size(); nodes.emplace_back(length); while (node != -1 && nodes[node].to[ch] == -1) { nodes[node].to[ch] = cur; node = nodes[node].link; } if (node == -1) { nodes[cur].link = 0; return; } int next_node = nodes[node].to[ch]; if (nodes[next_node].length == nodes[node].length + 1) { nodes[cur].link = next_node; return; } uint32_t clone = nodes.size(); nodes.emplace_back(nodes[node].length + 1); nodes[clone].link = nodes[next_node].link; nodes[clone].to = nodes[next_node].to; while (node != -1 && nodes[node].to[ch] == clone) { nodes[node].to[ch] = clone; node = nodes[node].link; } nodes[next_node].link = clone; nodes[cur].link = clone; } inline uint32_t char_to_uint(char ch) { return ch < 'a' ? ch - 'A' : ch - 'a'; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::vector<Node> nodes; nodes.reserve(100001); nodes.emplace_back(0); std::string str; str.reserve(100001); while (std::getline(std::cin, str)) { if (str[0] == 'A') { for (auto i = 2; i < str.size(); ++i) { add(char_to_uint(str[i]), nodes); } } else { int node = 0; size_t index = 2; uint32_t ch; while (index < str.size()) { ch = char_to_uint(str[index]); if (nodes[node].to[ch] == -1) { break; } node = nodes[node].to[ch]; ++index; } std::cout << (index == str.size() ? "YES" : "NO") << "\n"; } } return 0; }
Editor is loading...
Leave a Comment