Матч 313, Безпрефиксные деревья (PrefixFreeSets)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Для заданного набора слов необходимо найти такое его максимальное подмножество, для которого ни одно слово не является префиксом другого. Для входного набора слов вывести мощность такого максимального подмножества.

Класс: PrefixFreeSets

Метод: int maxElements(vector<string> words)

Ограничения: words содержит от 1 до 50 строк, каждая строка содержит от 1 до 50 символов ‘a’-‘z’.

Вход. Массив строк words.

Выход. Мощность максимального подмножества words, в котором ни одно слово не является префиксом другого.

Пример входа

words

{"hello","hi","h","run","rerun","running"}

{"a","b","cba","cbc","cbb","ccc”}

{"a","ab","abc","abcd","abcde","abcdef"}

Пример выхода

4

6

1

РЕШЕНИЕ

обработка строк

Необходимо перебрать все пары строк (words[i], words[j]), 0 £ i, j < words.size(), и если для некоторой пары words[i] будет префиксом words[j], то из списка слов следует удалить words[i]. Оставшееся множество слов в массиве words и будет искомым максимальным подмножеством. Возвращаем его размер.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

using namespace std;

class PrefixFreeSets{

public:

int maxElements(vector<string> words)

{

int i,j,flag;

for(i=0;i<words.size();)

{

flag = 0;

for(j=0;j<words.size();j++)

{

if (i == j) continue;

if (words[j].find(words[i]) == 0)

{

words.erase(words.begin()+i);

flag = 1; break;

}

}

if (!flag) i++;

}

return words.size();

}

};