Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
2.3 kB
2
Indexable
Never

#include <ios>
#include <iostream>
#include <string>
#include <vector>

static constexpr size_t ALPHABET_SIZE = 52;

struct Node {
    uint32_t length;
    int link{ -1 };
    std::vector<int> to;

    Node(uint32_t length): length(length), to(ALPHABET_SIZE, -1) {}
};

struct Tree {
    uint32_t last{ 0 };
    std::vector<Node> nodes;

    Tree(size_t capacity) {
        nodes.reserve(capacity + 1);
        nodes.emplace_back(0);
    }

    uint32_t last_length() const {
        return nodes[last].length;
    }
};

void add(uint32_t ch, Tree& tree) {
    int node = tree.nodes.size() - 1;
	uint32_t cur = tree.nodes.size();
    tree.nodes.emplace_back(tree.last_length() + 1);
    
    while (node != -1 && tree.nodes[node].to[ch] == -1) {
        tree.nodes[node].to[ch] = cur;
        node = tree.nodes[node].link;
    }

	if (node == -1) {
		tree.nodes[cur].link = 0;
		return;
	}

	int next_node = tree.nodes[node].to[ch];

	if (tree.nodes[next_node].length == tree.nodes[node].length + 1) {
		tree.nodes[cur].link = next_node;
		return;
	}

	uint32_t clone = tree.nodes.size();
	tree.nodes.emplace_back(tree.nodes[node].length + 1);
	tree.nodes[clone].link = tree.nodes[next_node].link;
	tree.nodes[clone].to = tree.nodes[next_node].to;

	while (node != -1 && tree.nodes[node].to[ch] == clone) {
		tree.nodes[node].to[ch] = clone;
		node = tree.nodes[node].link;
	}

	tree.nodes[next_node].link = clone;
	tree.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);

    Tree tree(100001);

    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]), tree);
            }
        } else {
            int node = 0;
            size_t index = 2;
            uint32_t ch;

            while (index < str.size()) {
                ch = char_to_uint(str[index]);
                if (tree.nodes[node].to[ch] == -1) {
                    break;
                }

                node = tree.nodes[node].to[ch];
                ++index;
            }

            std::cout << (index == str.size() ? "YES" : "NO") << "\n";
        }
    }

    return 0;
}
Leave a Comment