Разбор олимпиадной задачи — Проверка орфографии — 2

Технология и методы программирования Спортивное программирование Структуры данных Разбор олимпиадной задачи — Проверка орфографии — 2

  • В этой теме 0 ответов, 1 участник, последнее обновление 7 месяцев назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6078
      @admin
      StudLance.ru

      Условие задачи взято с сайта acmp.ru (Время: 1 сек. Память: 16 Мб Сложность: 39%):

      Время от времени каждому школьнику, изучающему английский язык, приходится сдавать учителю сочинение на английском языке. Учителя английского языка бывают разные. Когда школьник использует в сочинении слова, которые на уроках еще не проходили, одни восхищаются юным талантом, другие багровеют от злости и ставят двойку непослушному ученику, осмелившемуся кичиться своими знаниями.

      К сожалению, Ваша учительница из других. Она не потерпит ни малейшего отступления от использования словарного запаса. В этот раз еще одна беда обрушилась на Вашу голову. Сочинение, заданное на завтра контрольное сочинение по выученным словам. А это значит, что все слова, которые Вы выучили на уроках, должны присутствовать в сочинении хотя бы по одному разу.

      Таким образом, перед сдачей сочинения Вам необходимо проверить, что каждое слово в тексте сочинения встречается в словаре, и каждое слово из словаря встречается в тексте.

      Входные данные

      В первой строке входного файла INPUT.TXT находится два числа N и M (1 ≤ N ≤ 103, 1 ≤ M ≤ 105). В следующих N строках находится по одному слову из словаря. Все слова состоят из строчных английских букв. Длина каждого слова не превышает 20. Каждое слово состоит хотя бы из одного символа. Лишних пробелов перед словом и после него нет.

      В следующих M строках находится текст сочинения. Текст состоит из заглавных и строчных английских букв, пробелов и знаков препинания: точек (.), запятых (,), двоеточий (:), точек с запятыми (;), тире (-), апострофов ('), кавычек ("), восклицательных (!) и вопросительных (?) знаков.

      Общая длина текста не превосходит 104 символов. В данной задаче большие и маленькие буквы в словах не различаются.

      Выходные данные

      В выходной файл OUTPUT.TXT выведите «Everything is going to be OK.», если с сочинением все в порядке. Если не все слова из текста встречаются в словаре, выведите «Some words from the text are unknown.». Если же предыдущее неверно, но некоторые слова из словаря не встречаются в тексте, выведите «The usage of the vocabulary is not perfect.».

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 3 1
      am
      bill
      i
      I am Bill, am I?
      Everything is going to be OK.
      2 2 2
      seven
      day
      On the
      seventh day
      Some words from the text are unknown.
      3 4 1
      vocabulary
      wide
      too
      much
      Too wide vocabulary.
      The usage of the vocabulary is not perfect.

      Разбор решения задачи

      Задача посвящена структурам данных. Наибольшая трудоемкость задачи связана с многократным поиском слова в словаре. Нужно найти в нем каждое из M слов. Если организовать словарь как неупорядоченный массив — то потребуется N*M операций сравнения. Более оптимально — хранить словаь в виде сортированного вектора или дерева поиска. Для деревьев поиска в языке С++ можно использовать классы set и map (они реализуют красно-черные или AVL-деревья). В нашем случае наиболее правильным выбором будет map, т.к. помимо слов в словаре нужно фиксировать факт их использования.

      Другая проблема этой задачи — необходимость удаления (игнорирования) ряда символов. Наиболее простой в реализации вариант — создать свои собственные функции считывания слова, игнорирования пробелов (к которым отнести специальные символы) и т.п.:

      #include <fstream>
      #include <map>
      using namespace std;
      
      bool is_space(char c) {
        const string spaces(".,:;-'\"!?\n \t");
        return spaces.find(c) != std::string::npos;
      }
      
      void skip_spaces(istream& ist) {
        while (true) {
          if (ist.eof() || ist.bad())
            break;
          auto symbol = ist.peek();
          if (false == is_space(symbol))
            break;
          ist.get();
        }
      }
      
      string get_word(istream& ist) {
        string word;
        skip_spaces(ist);
      
        while (true) {
          if (ist.eof() || ist.bad())
            break;
      
          auto symbol = ist.peek();
          if (is_space(symbol))
            break;
      
          word.push_back(toupper(ist.get()));
        }
      
        return word;
      }
      
      int main() {
        std::ifstream ifst("input.txt");
        std::ofstream ofst("output.txt");
      
        size_t n, m;
        ifst >> n >> m;
      
        map<string, int> dict;
      
        for (size_t i = 0; i < n; ++i) {
          dict.insert(make_pair(get_word(ifst), 0));
        }
      
        while (true) {
          string word = get_word(ifst);
          if (word.empty())
            break;
      
          auto it = dict.find(word);
          if (it == dict.end()) {
            ofst << "Some words from the text are unknown.";
            return 0;
          }
          dict[word]++;
        }
      
        for (auto pair : dict) {
          if (pair.second == 0) {
            ofst << "The usage of the vocabulary is not perfect.";
            return 0;
          }
        }
      
        ofst << "Everything is going to be OK.";
      }

      В функции is_space объявлен статический массив «пробельных» символов, за счет этого он будет создан в одном экземпляре вне зависимости от того, сколько раз вызвана функция. Функция skip_spaces пропускает группу пробельных символов, а get_word — пропускает пробелы перед словом и считывает следующую группу символов до пробела (не включительно — за счет использования istream::peek). Кроме того, get_word переводит все символы в верхний регистр (это не очень хорошо с точки зрения чистоты кода — подумайте как можно улучшить).

      Однако, что не так в этом решении? — в стандартной библиотеке есть готовый istream::operator>>, который и считывает слово до пробела. Нужно как-то настроить поток, чтобы он считал знаки препинания за пробелы — тогда решение будет более красивым. За то, какой символ как «распознавать» отвечает локаль. Локаль имеет ряд масок (в том числе space), символы помещаются в таблицу, где к каждому из них прикрепляется набор масок. Чтобы изменить его — нужно создать класс-наследник от ctype<char>, например как показано ниже:

      #include <fstream>
      #include <vector>
      #include <algorithm>
      #include <map>
      #include <locale>
      using namespace std;
      
      struct Task997Whitespace : ctype<char> {
        static const mask* make_table() {
          static const string spaces(".,:;-'\"!?");
          static vector<mask> v(classic_table(), classic_table() + table_size);
      
          for (char symbol : spaces) {
            v[symbol] |= space;
          }
          return &v[0];
        }
      
        Task997Whitespace(std::size_t refs = 0)
          : ctype(make_table(), false, refs) {
        }
      };
      
      void str_toupper(std::string& s) {
          std::transform(s.begin(), s.end(), s.begin(),
            [](unsigned char c){ return std::toupper(c); } 
          );
      }
      
      int main() {
        std::ifstream ifst("input.txt");
        std::ofstream ofst("output.txt");
      
        ifst.imbue(std::locale(ifst.getloc(), new Task997Whitespace()));
      
        size_t n, m;
        ifst >> n >> m;
      
        map<string, int> dict;
      
        for (size_t i = 0; i < n; ++i) {
          string word;
          ifst >> word;
          str_toupper(word);
          dict.insert(std::make_pair(word, 0));
        }
      
        while (true) {
          string word;
          ifst >> word;
          str_toupper(word);
          if (word.empty())
            break;
      
          auto it = dict.find(word);
          if (it == dict.end()) {
            ofst << "Some words from the text are unknown.";
            return 0;
          }
          dict[word]++;
        }
      
        for (auto pair : dict) {
          if (pair.second == 0) {
            ofst << "The usage of the vocabulary is not perfect.";
            return 0;
          }
        }
      
        ofst << "Everything is going to be OK.";
      }

      Теперь для преобразования строки в верхний регистр применяется алгоритм transform.

      Кроме того, для удаления лишних символов из файла можно скопировать содержимое файла в строку (стандартным алгоритмом copy)

      copy(std::istreambuf_iterator<char>(ifst), istreambuf_iterator<char>(),
        insert_iterator<string>(file_str, file_str.begin())
      );

      Заменить в ней специальные знаки на пробелы:

      std::replace_if(file_str.begin(), file_str.end(), [](char c) {
          const string spaces(".,:;-'\"!?");
          return spaces.find(c) != std::string::npos;
      }, ' ');

      Перевести символы в веоррхний регистр:
      transform(file_str.begin(), file_str.end(), file_str.begin(), ::toupper);

      Поместить в строковый поток и дальше работать с ним:

      std::stringstream sstr;
      sstr << file_str;

      Вариант с удалением символов из строки не пройдет, т.к. слова в тексте иногда могут разделяться только знаками препинания — в этих случаях при удалении слова «сольются».

      file_str.erase(std::remove_if(file_str.begin(), file_str.end(), [](char c) {
        const string spaces(".,:;-'\"!?");
        return spaces.find(c) != std::string::npos;
      }), file_str.end());

      Последнее «улучшение» — можно обойтись без этой строки, хранящей весь файл целиком, а копировать непосредственно из файла в строковый поток:

      #include <fstream>
      #include <algorithm>
      #include <map>
      #include <iterator>
      #include <sstream>
      using namespace std;
      
      int main() {
        std::ifstream ifst("input.txt");
        std::ofstream ofst("output.txt");
        std::stringstream sstr;
      
        size_t n, m;
        ifst >> n >> m;
      
        map<string, int> dict;
      
        transform(std::istreambuf_iterator<char>(ifst), istreambuf_iterator<char>(),
                  std::ostreambuf_iterator<char>(sstr), [](char c) -> char {
          const string spaces(".,:;-'\"!?");
          if (spaces.find(c) != std::string::npos)
            return ' ';
          return ::toupper(c);
        });
      
        for (size_t i = 0; i < n; ++i) {
          string word;
          sstr >> word;
          dict.insert(std::make_pair(word, 0));
        }
      
        while (true) {
          string word;
          sstr >> word;
      
          if (word.empty())
            break;
      
          auto it = dict.find(word);
          if (it == dict.end()) {
            ofst << "Some words from the text are unknown.";
            return 0;
          }
          dict[word]++;
        }
      
        for (auto pair : dict) {
          if (pair.second == 0) {
            ofst << "The usage of the vocabulary is not perfect.";
            return 0;
          }
        }
      
        ofst << "Everything is going to be OK.";
      }

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×