Список телефонных номеров (Editorial)

Реализуем структуру данных — бор (префиксное дерево) и занесём в неё все телефонные номера. Если в вершине бора заканчивается слово, пометим её флагом leaf = 1.

При добавлении очередного номера $s$ в бор проверим два условия:

• не является ли $s$ префиксом какого-либо уже добавленного номера;

• не существует ли номера, который является префиксом самого $s$.

Также отдельно проверим, нет ли в списке полностью совпадающих телефонных номеров.

Если ни одно из этих условий не выполняется, то входной набор телефонных номеров считается совместимым.

Пример

Пусть в бор уже добавлен номер телефона $911$. Если далее встретится номер $9112$, то при его вставке мы дойдём до вершины $3$, которая уже помечена как конечная. Это означает, что для номера $9112$ уже существует другой номер, являющийся его префиксом.

Рассмотрим другой случай: пусть следующим номером будет $91$. После его вставки мы окажемся в вершине $2$. Однако из этой вершины существует переход в другие вершины (например, в вершину $3$). Это значит, что номер $91$ является префиксом номера, который уже был ранее добавлен в бор.

Реализация алгоритма

Пусть item — структура, описывающая вершину бора. Алфавит бора состоит из цифр от $0$ до $9$. Структура содержит конструктор, который при создании вершины инициализирует все указатели значением $-1$.

struct item
{
  int next[10];
  int leaf;
  item() 
  {
    for (int i = 0; i < 10; i++) next[i] = -1;
    leaf = 0;
  }
};

Бор хранится в массиве $trie$.

vector<item> trie;

Функция Insert вставляет в бор телефонный номер, заданный строкой $s$. Если во время вставки обнаруживается несовместимость номеров (например, один номер является префиксом другого), функция возвращает false. В противном случае возвращает true.

bool Insert(string &s)
{
  int v = 0;

Проходим по всем символам строки $s$, вставляя её в бор.

  for (char ch : s)
  {

Рассматриваем текущий символ $ch$ строки $s$, которому соответствует цифра $d$.

    int d = ch - '0';

Если из теущей вершины trie[v] нет перехода по символу $d$, создаем новую вершину бора.

    if (trie[v].next[d] == -1)
    {
      trie[v].next[d] = trie.size();
      trie.push_back(item());
    }

Выполняем переход по символу $d$ к следующей вершине.

    v = trie[v].next[d];

Если вершина $v$ является концом какого-то другого слова (leaf = 1), то новое вставляемое слово $s$ имеет в качестве префикса уже существующее слово. А это недопустимо по условию задачи. Номера не должны быть префиксами друг друга. Возвращаем false.

    if (trie[v].leaf) return false;
  }

Обработка строки $s$ завершена. Если из текущей вершины trie[v] можно перейти хотя бы в одну другую вершину (то есть существует индекс $i$, для которого trie[v].next[i] \ne -1), значит, уже было добавлено слово, для которого $s$ является префиксом.

  for (int i = 0; i < 10; i++)
    if (trie[v].next[i] != -1) return false;

Отмечаем завершение слова $s$ в текущей вершине trie[v], устанавливая соответствующий флаг.

  trie[v].leaf = true;
  return true;
}

Основная часть программы. Читаем входные данные.

cin >> tests;
while (tests--)
{
  cin >> n;

Очищаем бор и устанавливаем его размер равным единице — изначально в боре содержится только одна вершина (корень). Поскольку все телефонные номера изначально считаются совместимыми, переменной $flag$ присваивается значение $0$.

  trie.clear(); trie.resize(1);
  flag = 0;

Читаем все телефонные номера и поочерёдно заносим их в бор. Даже если на каком-то этапе была обнаружена несовместимость номеров, необходимо продолжить чтение оставшихся номеров до конца, так как входные данные могут содержать несколько тестов.

  for (i = 0; i < n; i++)
  {
    cin >> s;
    if (!Insert(s)) flag = 1;
  }  

После обработки всех номеров выводим результат в зависимости от значения переменной $flag$.

  if (flag) cout << "NO" << endl;
  else cout << "YES" << endl;
}