Тема: Чтение строк C++
Нужно реализовать структуру данных, поддерживающую множество строк.
Поступает N запросов вида
<команда> <строка>
1 <= N <= 2*10^5
С хранением все ясно -- либо бор, либо хэш таблица.
Однако как быстро считывать строки??
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Чтение строк C++
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Нужно реализовать структуру данных, поддерживающую множество строк.
Поступает N запросов вида
<команда> <строка>
1 <= N <= 2*10^5
С хранением все ясно -- либо бор, либо хэш таблица.
Однако как быстро считывать строки??
а что я не так делаю, что у меня не компилится?
#include <stdio.h>
#include <set>
using namespace std;
set < char [10] > s;
int main()
{
char string[10];
char c;
while (scanf("%c", &c)){
char space;
scanf("%c", &space);
gets(string);
if (c == '?')
if (s.find(string) != s.end()) printf("YES\n");
else printf("NO\n");
else s.insert(string);
}
return 0;
}
Нельзя делать set из массивов. Вообще стандартные STL-ные контейнеры не умеют работать с массивами. Так что или делать свою структурку для строк, или работать с указателями на строчки char*, или использовать STL-ную string.
а не можете показать на примере с кодом как работать с char* (т.е. чтение и добавление) ^^ ?
Конечно
char * str = new char[1000]; // выделение памяти под 999 символов, например
gets (str); // чтение строки
s.insert (str); // добавление в set
Но кроме этого, нужно научить set работать со строками: пока он воспринимает их только как указатели (т.е. будет сравнивать их по адресу в памяти). Нам же надо сранивать их посимвольно, поэтому делаем новый компаратор для сета:
struct cmp {
bool operator() (char *a, char *b) {
return strcmp (a, b) < 0;
}
};
set < char*, cmp > s;
По-хорошему, память, выделенную по new, надо в конце освобождать по delete, но в олимпиадных задачах на это можно забить.
ОГРОМНОЕ спасибо!!
помню, приходилось на делфях писать задачки на хэши)
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Чтение строк C++