Разбор олимпиадной задачи — Секретное сообщение

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

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

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

      На секретную базу в Арктике поступила шифровка – последовательность из n десятичных цифр. Она содержит номер секретной базы в Антарктиде, который является последовательностью из k десятичных цифр. При этом для того, чтобы отличить его от ненужной Вам информации, он повторен в шифровке хотя бы два раза (возможно, эти два вхождения перекрываются).

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

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

      Первая строка входного файла INPUT.TXT содержит два целых числа: n (1 ≤ n ≤ 10^5) и k (1 ≤ k ≤ 5) – длину шифровки и длину номера секретной базы соответственно. Вторая строка содержит n цифр – шифровку. Помните, что цифры в шифровке не разделяются пробелами.

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

      В выходной файл OUTPUT.TXT выведите «YES», если шифровка содержит номер секретной базы, и «NO» в противном случае.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 10 5
      0123456789
      NO
      2 13 2
      0123400056789
      YES

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

      В задаче требуется найти в исходной строке все подстроки длиной k и посмотреть есть ли среди них две одинаковые. Схематично задача показана на рисунке:

      В строке из n символов существует n-k+1 подстрока длины k. Алгоритм, выполняющий попарный перебор и сравнение подстрок будет иметь трудоемкость O(n^2). Для заданных ограничений он явно не пройдет по времени.

      Будем хранить все обработанные подстроки, причем в упорядоченном виде. Множество (std::set) в С++ внутри реализуется через сбалансированное дерево. Операции вставки и поиска требуют порядка O(log(n)) операций (вместо O(n)), значит весь алгоритм потребует O(n*log(n)) операций. Это значительно лучше:

      #include <fstream>
      #include <string>
      #include <set>
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        set<string> all_substrings;
      
        size_t n, k;
        ifst >> n >> k;
      
        string message;
        ifst >> message;
      
        for (size_t i = 0; i <= n-k; ++i) {
          string substring = message.substr(i, k);
          if (all_substrings.find(substring) != all_substrings.end()) {
            ofst << "YES";
            return 0;
          }
          all_substrings.insert(substring);
        }
      
        ofst << "NO";
      }

      Вместо std::set тут можно было бы использовать упорядоченный вектор и алгоритм двоичного поиска (std::binary_search).

      Приведенный алгоритм работает быстрее лишь за счет ускорения операции поиска, однако, в этой задаче можно полностью избежать сравнения строк. Значение k ограничено небольшим числом, а вне зависимости от длины исходной строки n, возможно m = 10^k подстрок длины k — ведь в подстроке могут присутствовать только цифры. Значит, возможно завести булевый массив длины m, каждая подстрока будет задавать индекс элемента в этом массиве — например подстрока "0123" соответствует 123-ему элементу массива. Теперь, чтобы проверить «встречалась ли такая подстрока ранее» мы вместо сравнения строк проверим значение соответствующего элемента. Такая структура данных называется bitmap (Битовая карта).

      #include <fstream>
      #include <string>
      #include <sstream>
      #include <vector>
      #include <cmath>
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        vector<bool> bitmap;
      
        size_t n, k, index;
        ifst >> n >> k;
      
        bitmap.resize(static_cast<size_t>(pow(10, k)), false);
      
        string message;
        ifst >> message;
      
        for (size_t i = 0; i <= n-k; ++i) {
          stringstream sstr;
          sstr << message.substr(i, k);
          sstr >> index;
      
          if (bitmap[index]) {
            ofst << "YES";
            return 0;
          }
          bitmap[index] = true;
        }
      
        ofst << "NO";
      }

      Для преобразования строки в число тут используется строковый поток (stringstream).

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