858D - Polycarp's phone book - CodeForces Solution

//
// Copyright 2023 Turing Edu. All Rights Reserved.
//
// FileName: 858D.cc
// Author: Beiyu Li <[email protected]>
// Date: 2023-03-17
//
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;

const int maxn = 70000 + 5;
const int mod = 19260817;

int n;
char s[maxn][11];
int h[maxn][10], p10[10];
int cnt[mod];
pair<int, int> ret[maxn];

int Hash(int i, int l, int r) {
  return (h[i][r] - (LL)h[i][l-1] * p10[r-l+1] % mod + mod) % mod;
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%s", s[i] + 1);
    for (int j = 1; j <= 9; ++j)
      h[i][j] = (h[i][j-1] * 10 + s[i][j] - '0') % mod;
  }
  for (int j = 0; j < 10; ++j) p10[j] = (j? p10[j-1] * 10 % mod: 1);
  for (int l = 1; l <= 9; ++l) {
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
      for (int j = 1; j + l <= 10; ++j) ++cnt[Hash(i,j,j+l-1)];
    for (int i = 0; i < n; ++i) {
      if (ret[i].first) continue;
      for (int j = 1; j + l <= 10; ++j)
        if (!--cnt[Hash(i,j,j+l-1)]) ret[i] = make_pair(j, l);
      for (int j = 1; j + l <= 10; ++j) ++cnt[Hash(i,j,j+l-1)];
    }
  }
  for (int i = 0; i < n; ++i) {
    s[i][ret[i].first+ret[i].second] = 0;
    printf("%s\n", s[i] + ret[i].first);
  }

  return 0;
}