Untitled
unknown
plain_text
a year ago
8.3 kB
3
Indexable
#include <ios> #include <iostream> #include <string> #include <vector> std::string SS; void print(int l, int r, const std::vector<uint8_t> &str) { while (l < r) { std::cout << static_cast<char>('a' + str[l]); ++l; } std::cout << "\n"; } struct Result { size_t size{ 0 }; std::vector<std::pair<uint32_t, uint32_t>> items; }; Result out; int FULL_MASK = 0; int ALPHABET_SIZE = 26; struct Node { uint32_t l; uint32_t r; int parent{-1}; int link{-1}; int shift{-1}; int number{ -1 }; std::vector<int> to; Node(uint32_t l, uint32_t r, int parent = -1) : l(l), r(r), parent(parent), to(ALPHABET_SIZE, -1) {} uint32_t size() const { return r - l; } }; struct State { int node; uint32_t pos; State(int node, uint32_t pos) : node(node), pos(pos) {} }; State transmit(State state, uint32_t l, uint32_t r, std::vector<Node> &nodes, const std::vector<uint8_t> &str) { while (l < r) { auto &node = nodes[state.node]; if (state.pos == node.size()) { state.node = node.to[str[l]]; state.pos = 0; if (state.node == -1) { return state; } } else { if (str[node.l + state.pos] != str[l]) { return State(-1, 0); } if (r - l < node.size() - state.pos) { return State(state.node, state.pos + r - l); } l += node.size() - state.pos; state.pos = node.size(); } } return state; } uint32_t split(const State &state, std::vector<Node> &nodes, const std::vector<uint8_t> &str) { auto &node = nodes[state.node]; if (state.pos == node.size()) { return state.node; } if (state.pos == 0) { return node.parent; } uint32_t id = nodes.size(); nodes.emplace_back(node.l, node.l + state.pos, node.parent); nodes[node.parent].to[str[node.l]] = id; nodes[id].to[str[node.l + state.pos]] = state.node; node.parent = id; node.l += state.pos; // std::cout << "S1: "; // print(nodes[id].l, nodes[id].r, str); // std::cout << "S2: "; // print(node.l, node.r, str); return id; } int get_link(int node_id, std::vector<Node> &nodes, const std::vector<uint8_t> &str) { auto &node = nodes[node_id]; if (node.link != -1) { return node.link; } if (node.parent == -1) { return 0; } auto to = get_link(node.parent, nodes, str); auto state = transmit(State(to, nodes[to].size()), node.l + (node.parent == 0), node.r, nodes, str); node.link = split(state, nodes, str); return node.link; } void add(int number, int pos, State &state, std::vector<Node> &nodes, const std::vector<uint8_t> &str) { while (true) { auto st = transmit(state, pos, pos + 1, nodes, str); if (st.node != -1) { state = st; return; } int mid = split(state, nodes, str); auto leaf = nodes.size(); nodes.emplace_back(pos, str.size(), mid); nodes[mid].to[str[pos]] = leaf; nodes[leaf].shift = pos - nodes[mid].size(); nodes[leaf].number = number; //nodes[mid].number = -1; state.node = get_link(mid, nodes, str); state.pos = nodes[state.node].size(); // std::cout << "leaf: " << number << " "; // print(nodes[leaf].l, nodes[leaf].r, str); if (mid == 0) { nodes[leaf].shift = pos; //nodes[leaf].number = number; break; } } } bool compare(const Result& v1, const Result& v2, const std::vector<uint8_t>& str) { int i1 = 0; int i2 = 0; int l1 = v1.items[0].first; int r1 = v1.items[0].second; int l2 = v2.items[0].first; int r2 = v2.items[0].second; while (i1 < v1.items.size() && i2 < v2.items.size()) { if (l1 >= r1) { ++i1; if (i1 >= v1.items.size()) { break; } l1 = v1.items[i1].first; r1 = v1.items[i1].second; } if (l2 >= r2) { ++i2; if (i2 >= v2.items.size()) { break; } l2 = v2.items[i2].first; r2 = v2.items[i2].second; } if (str[l1] == str[l2]) { ++l1; ++l2; continue; } return str[l1] > str[l2]; } return false; } int func(int n, const std::vector<Node> &nodes, const std::vector<uint8_t> &str, Result& res) { const auto &node = nodes[n]; // auto xx = SS.substr(node.l, node.size()); // std::cout << "node: " << n << ", number: " << node.number << " " << xx << "\n"; if (node.number == -1) { for (uint32_t i = node.l; i < node.r; ++i) { if (str[i] >= 26) { throw std::exception(); } } if (node.size() > 0) { res.size += node.size(); res.items.emplace_back(node.l, node.r); } int mask = 0; for (size_t i = 0; i < node.to.size(); ++i) { if (node.to[i] != -1) { mask |= func(node.to[i], nodes, str, res); } } if (mask == FULL_MASK && res.size > 0 && (res.size > out.size || (res.size == out.size && compare(res, out, str)))) { out = res; } if (node.size() > 0) { res.size -= node.size(); res.items.resize(res.items.size() - 1); } return mask; } else { return (1 << node.number); } // size_t size = 0; // int mask = 0; // for (uint32_t i = node.l; i < node.r; ++i) { // if (mask == 0 && str[i] < 26) { // ++size; // } // if (str[i] >= 26) { // mask |= (1 << (str[i] - 26)); // break; // } // } // if (mask != 0) { // return mask; // } // if (size > 0) { // res.size += size; // res.items.emplace_back(node.l, size); // } // for (size_t i = 0; i < node.to.size(); ++i) { // if (node.to[i] != -1) { // mask |= func(node.to[i], nodes, str, res); // } // } // if (mask == FULL_MASK && out.size < res.size) { // out = res; // } // if (size > 0) { // res.size -= size; // res.items.resize(res.items.size() - 1); // } // return mask; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int K; std::cin >> K; if (K == 1) { std::string s; std::getline(std::cin, s); std::getline(std::cin, s); std::cout << s << "\n"; return 0; } ALPHABET_SIZE += K; std::vector<uint8_t> str(200001 * K, 0); int size = 0; char ch; std::cin.get(ch); while (K > 0) { std::cin.get(ch); if (ch == '\n') { FULL_MASK <<= 1; FULL_MASK |= 1; --K; str[size] = K + 26; SS.push_back(K + '0'); ++size; continue; } SS.push_back(ch); str[size] = ch - 'a'; ++size; } // std::vector<std::string> data = {"abacaba", "mycabarchive", "acabistrue"}; // int K = data.size(); // if (K == 1) { // std::cout << data[0] << "\n"; // return 0; // } // ALPHABET_SIZE += K; // std::vector<uint8_t> str(200001 * K, 0); // int size = 0; // for (int i = 0; i < data.size(); ++i) { // const auto& s = data[i]; // for (int j = 0; j < s.size(); ++j) { // str[size] = s[j] - 'a'; // ++size; // } // FULL_MASK <<= 1; // FULL_MASK |= 1; // str[size] = data.size() - 1 - i + 26; // ++size; // } // int x = data.size() - 1; // for (int i = 0; i < size; ++i) { // if (str[i] >= 26) { // SS.push_back(x + '0'); // --x; // } else { // SS.push_back(str[i] + 'a'); // } // } str.resize(size); State state(0, 0); // std::cout << "size: " << size << " "; // print(0, size, str); std::vector<Node> nodes; nodes.reserve(size * 2); nodes.emplace_back(0, 0, -1); int number = ALPHABET_SIZE - 27; for (size_t i = 0; i < str.size(); ++i) { add(number, i, state, nodes, str); if (str[i] >= 26) { --number; } } Result res; res.items.reserve(100000); func(0, nodes, str, res); if (out.size > 0) { for (size_t i = 0; i < out.items.size(); ++i) { for (int begin = out.items[i].first; begin < out.items[i].second; ++begin) { std::cout << static_cast<char>('a' + str[begin]); } } } std::cout << "\n"; return 0; }
Editor is loading...
Leave a Comment