2303. Список телефонных номеров
По
заданному списку телефонных номеров определить, является ли он совместимым в
том смысле, что ни один номер не является префиксом другого. Пусть, например,
телефонный каталог содержит следующие номера:
·
Экстренная служба 911
·
Алиса 97 625 999
·
Боб 91 12 54 26
В этом
случае не представляется возможным позвонить Бобу, потому что после набора трех
цифр телефона Боба Вы сразу же попадете в Экстренную службу. Приведенный список
является несовместимым.
Вход. Первая строка содержит количество
тестов t (1 ≤ t ≤ 40). Каждый тест начинается
строкой, содержащей количество телефонных номеров n (1 ≤ n ≤ 106).
Каждая из следующих n строк содержит
один телефонный номер. Телефонный номер содержит не более десяти цифр.
Выход. Для каждого теста вывести “YES”, если список телефонных номеров
является совместным, и “NO” иначе.
|
Пример
входа |
Пример
выхода |
|
2 3 911 97625999 91125426 5 113 12340 123440 12345 98346 |
NO YES |
РЕШЕНИЕ
структуры данных – бор
Анализ алгоритма
Реализуем
структуру данных бор. Занесем в нее номера телефонов. Если в вершине бора
заканчивается слово, то установим в ней leaf
= 1.
При занесении
очередного слова s в бор проверяем,
является ли оно префиксом какого-нибудь слова или существует какое-нибудь
слово, являющееся префиксом s.
Отдельно проверяем, не совпадают ли два телефонных номера в списке.
Если описанные
случаи не имеют места, то входной набор телефонных номеров является совместимым.
Пример
Пусть в бор
занесен телефон 911. Если далее встретится номер 9112, то при вставке его в бор
мы окажемся в вершине 3, которая уже является финальной. Следовательно для
номера 9112 уже имеется другой номер, являющийся его префиксом.
Пусть следующим
номером будет 91. После его вставки в бор мы окажемся в вершине 2. Однако из
вершины 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, в бор. Переменная flag устанавливается в 1, если обнаруживается несоответствие
номеров.
void Insert(char
*s)
{
int i, v = 0;
item temp;
if (flag) return;
Проходим по всем символам слова s, вставляя его в бор.
for (i = 0; i
< strlen(s); ++i)
{
Если текущее слово s еще не обработано до конца, а мы уже
находимся в вершине trie[v],
являющейся концом некоторого другого слова t,
то t является префиксом s. Набор телефонных номеров является
несовместным, устанавливаем flag
равным 1.
if
(trie[v].leaf) {flag = 1; return;}
char c =
s[i] - '0';
Если из теущей вершины trie[v] нет перехода по символу c, то создаем новую вершину бора.
if
(trie[v].next[c] == -1)
{
trie[v].next[c] = trie.size();
trie.push_back(temp);
}
Совершаем переход по символу c.
v = trie[v].next[c];
}
Обработка слова s закончена. Если из текущей вершины trie[v] можно попасть еще куда-нибудь (существует i, для которого trie[v].next[i] ≠ -1), то существует слово t, для которого s будет префиксом. Устанавливаем flag = 1.
for(i = 0; i
< 10; i++)
if
(trie[v].next[i] != -1) flag = 1;
Если обработка слова s закончена в вершине, которая уже
является концом некоторого телефонного номера t, то номера s и t совпадают.
if
(trie[v].leaf) flag = 1;
Отмечаем факт завершения обработки
слова s в вершине trie[v].
trie[v].leaf = true;
}
Основная часть
программы. Читаем входные данные.
scanf("%d",&t);
while(t--)
{
scanf("%d\n",&n);
Чистим бор. Устанавливаем его длину равной единице: это
единственная вершина – корень бора. Изначально все телефонные номера считаются
совместимыми, присваиваем переменной flag значение 0.
trie.clear(); trie.resize(1);
flag = 0;
Читаем телефонные номера. Заносим их
в бор. Даже если на каком-то этапе обнаружена несовместимость номеров – все
равно следует дочитать номера до конца, так как входные данные содержат
несколько тестов.
for(i = 0; i
< n; i++)
{
gets(number);
Insert(number);
}
В зависимости от значения flag выводим ответ.
if (flag)
printf("NO\n"); else printf("YES\n");
}
Реализация при помощи класса
Объявим класс
Node – вершина бора. Значение leaf = 1, если текущая вершина является
концом какого-нибудь слова. Значение out = 1, если из текущей вершины
имеются исходящие ребра (слово, заканчивающееся в текущей вершине, является
префиксом некоторого другого слова).
class Node
{
public:
int next[10];
int out,
leaf;
Node()
{
for(int i = 0; i < 10; i++) next[i] = -1;
out = leaf = 0;
}
};
Объявим класс Trie. Элементы бора храним в векторе trie.
class Trie
{
public:
vector<Node> trie;
Trie()
{
trie.clear();
trie.resize(1);
}
Вставка слова s в бор.
void Insert(char *s)
{
int v = 0;
for (int i = 0; i < strlen(s); ++i)
{
char c =
s[i]-'0';
if
(trie[v].next[c] == -1)
{
trie[v].next[c] = trie.size();
trie[v].out++;
trie.push_back(Node());
}
v = trie[v].next[c];
}
trie[v].leaf ++;
}
Функция CheckTrie проверяет,
является ли набор слов в боре совместимым. То есть никакая вершина не должна
быть окончанием более одного слова (trie[i].leaf ≤ 1). А
также следует проверить, что никакое слово, оканчивающееся в вершине i,
не является префиксом никакого другого
слова.
int
CheckTrie(void)
{
for(int i = 0; i < trie.size(); i++)
if
((trie[i].leaf > 1) || ((trie[i].leaf == 1) && (trie[i].out)))
return
1;
return 0;
}
};
Создадим указатель на бор.
Trie *t;
Основная часть
программы. Читаем входные данные.
scanf("%d",&tests);
while(tests--)
{
scanf("%d\n",&n);
Для каждого следующего теста создаем
новый бор.
t = new
Trie();
Читаем входные номера телефонов,
заносим их в бор.
for(int i = 0; i < n; i++)
{
gets(number);
t->Insert(number);
}
Проверяем набор телефонных номеров на
совместимость.
if
(t->CheckTrie()) printf("NO\n");
else printf("YES\n");
}
Реализация без STL, бор моделируем
массивом
Пусть node – структура
вершины бора. Она содержит:
·
10 указателей next[i] на цифры от 0 до 9.
·
Переменная leaf содержит количество слов, которые заканчиваются в вершине.
·
Переменная out содержит количество указателей, исходящих из вершины.
Бор содержит до
106 слов, каждое из
которых состоит из не более 10 символов. Следовательно размер бора не более MAX = 106 * 10 = 107.
#define MAX 10000001
struct node
{
int next[10];
int out, leaf;
};
Объявим бор tries как массив структур node. Размер бора
храним в переменной TrieSize.
node tries[MAX];
int TrieSize;
Функция init добавляет вершину в бор. В переменные leaf и out заносим 0. Указатели next[i] инициализируем
значением -1.
int init(void)
{
tries[TrieSize].leaf = 0;
tries[TrieSize].out = 0;
for(int i = 0; i < 10; i++)
tries[TrieSize].next[i] = -1;
return
TrieSize++;
}
Функция Insert вставляет в бор номера телефона, заданный в строке s.
void Insert(string &s)
{
Корень бора находится в вершине v =
0.
int v = 0;
Проходим по всем символам слова s, вставляя его в бор.
for (int i = 0; i < s.size(); i++)
{
Извлекаем следующий символ c из строки s.
char c = s[i] - '0';
Если из теущей вершины trie[v] нет перехода по символу c, то создаем новую вершину бора.
if (trie[v].next[c] == -1)
trie[v].next[c] = init();
trie[v].out++;
Совершаем переход по символу c.
v = trie[v].next[c];
}
В вершине v завершается обработка слова s.
trie[v].leaf++;
}
Функция CheckTrie проверяет,
является ли набор слов в боре совместимым. То есть никакая вершина не должна
быть окончанием более одного слова (trie[i].leaf ≤ 1). А
также следует проверить, что никакое слово, оканчивающееся в вершине i,
не является префиксом никакого другого
слова.
int CheckTrie(void)
{
for (int i = 0; i < TrieSize; i++)
if ((trie[i].leaf > 1)
|| ((trie[i].leaf == 1) && (trie[i].out)))
return 0;
return 1;
}
Основная часть
программы. Читаем входные данные. Обрабатываем test тестов.
cin >> test;
while (test--)
{
cin >> n;
Инициализируем бор. Устанавливаем его длину равной единице:
это единственная вершина – корень бора.
TrieSize = 0;
init();
Читаем телефонные номера. Заносим их
в бор. Даже если на каком-то этапе обнаружена несовместимость номеров – все
равно следует дочитать номера до конца, так как входные данные содержат
несколько тестов.
for(i = 0; i
< n; i++)
{
cin >> s;
Insert(s);
}
Проверяем набор телефонных номеров на
совместимость и выводим ответ.
if (CheckTrie()) cout << "YES" << endl;
else cout << "NO" << endl;
}