Untitled

 avatar
unknown
plain_text
a year ago
7.6 kB
3
Indexable


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


//std::string SS;

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;
  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();

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

uint8_t 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()) {
    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] ? 1 : 2;
  }

  return 0;
}

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 << "number: " << node.number << "   " << xx << "\n"; 


    if (node.number == -1) {
        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 > out.size || (res.size == out.size && compare(res, out, str) == 1))) {
              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;
      ++size;
      continue;
    }

    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::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) {
    if (str[i] >= 26) {
        --number;
    }

    add(number, i, state, nodes, str);
  }

  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