Untitled

 avatar
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