Untitled

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

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;

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

    if (mid == 0) {
      nodes[leaf].shift = pos;
      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];

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

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;
  }

  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) {
    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;
}