Untitled

mail@pastecode.io avatar
unknown
plain_text
3 months ago
5.1 kB
2
Indexable
Never




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


std::string res;
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};
  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;
  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 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();

    state.node = get_link(mid, nodes, str);
    state.pos = nodes[state.node].size();

    if (mid == 0) {
      nodes[leaf].shift = pos;
      break;
    }
  }
}

int func(int n, const std::vector<Node>& nodes, const std::vector<uint8_t>& str, std::string& tmp) {
    const auto& node = nodes[n];
    size_t size = tmp.size();

    int mask = 0;

    for (uint32_t i = node.l; i < node.r; ++i) {
        if (mask == 0 && str[i] < 26) {
            tmp.push_back(str[i] + 'a');
        }

        if (str[i] >= 26) {
            mask |= (1 << (str[i] - 26));
            break;
        }
    }

    if (mask != 0) {
        if (size < tmp.size()) {
            tmp.resize(size);
        }

        return mask;
    }

    for (int i = 0; i < node.to.size(); ++i) {
        if (node.to[i] != -1) {
            mask |= func(node.to[i], nodes, str, tmp);
        }
    }

    // if (mask == FULL_MASK) {
    //     std::cout << tmp << "\n";
    // }

    if (mask == FULL_MASK && res.size() < tmp.size()) {
        res = tmp;
    }

    if (size < tmp.size()) {
        tmp.resize(size);
    }

    return mask;
}






int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

    int K;
    std::cin >> K;

    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;
            ++size;
            continue;
        }

        str[size] = ch - 'a';
        ++size;
    }


    // int K = 3;
    // std::vector<std::string> data = { "abacaba", "mycabarchive", "acabistrue" };
    // ALPHABET_SIZE += K;

    // std::vector<uint8_t> str(200001*K, 0);
    // int size = 0;

    // for (int i = 0; i < data.size(); ++i) {
    //     FULL_MASK <<= 1;
    //     FULL_MASK |= 1;

    //     for (int j = 0; j < data[i].size(); ++j) {
    //         str[size] = data[i][j] - 'a';
    //         ++size;
    //     }

    //     str[size] = i + 26;
    //     ++size;
    // }





    str.resize(size);
    State state(0, 0);

    std::vector<Node> nodes;
    nodes.reserve(size*2);
    nodes.emplace_back(0, 0, -1);

    for (size_t i = 0; i < str.size(); ++i) {
        add(i, state, nodes, str);
    }

    for (int i = 0; i < 26; ++i) {
        if (nodes[0].to[i] != -1) {
            std::string tmp;
            func(nodes[0].to[i], nodes, str, tmp);
        }
    }

    std::cout << res << "\n";
    return 0;
}
Leave a Comment