TCHS 08, Раунд 2, Фильтр (QueryFilter)

Строка query содержит текст – набор слов, разделенных пробелами. Вам необходимо совершить следующие операции:

1. Удалить из текста все слова, содержащиеся в массиве common;

2. Удалить повторяющиеся слова;

3. Отсортировать слова в лексикографическом порядке;

Результирующий набор слов вернуть в виде массива строк.

Класс: QueryFilter

Метод: vector<string> preprocess(string query,

vector<string> common)

Ограничения: query содержит от 1 до 50 пробелов и символов ‘a’ – ‘z’, common содержит от 1 до 50 строк, состоящих из букв ‘a’ – ‘z’, все слова в common разные.

Вход. Строка query и массив строк common.

Выход. Массив строк, получающихся после выполнения операций 1, 2, 3 над текстом query.

Пример входа

query	common
"an easy test"	{"a", "an", "the"}
"some really cool stuff that i forgot where to look"	{"i", "the", "to", "a", "an", "that"}
"aaaaaaaaaaaaaaaa"	{"a"}

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

{"easy", "test"}

{"cool", "forgot", "look", "really", "some", "stuff", "where"}

{"aaaaaaaaaaaaaaaa"}

РЕШЕНИЕ

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

Выделяем из строки query набор слов при помощи потокового ввода stringstream. Заносим слова во множество s. Повторяющиеся слова удаляются автоматически. Одновременно происходит сортировка слов в лексикографическом порядке. Проходим по массиву common и удаляем все слова, встречающиеся в нем, из множества s. Создаем искомый массив строк res при помощи конструктора копирования (все слова из множества s копируются в res в том же порядке, в котором они находятся в s, то есть в лексикографическом). Возвращаем массив res.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <set>

#include <sstream>

using namespace std;

set<string> s;

class QueryFilter

{

public:

vector<string> preprocess(string query, vector<string> common)

{

string a;

int i;

stringstream in(query);

while(in >> a) s.insert(a);

for(i=0;i<common.size();i++) s.erase(common[i]);

vector<string> res(s.begin(),s.end());

return res;

}

};