2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему
 
 Циклическая строка
Сообщение18.12.2016, 02:59 


07/03/13
22
Приветствую.

Есть такая задача: http://informatics.mccme.ru/mod/stateme ... id=12475#1

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

Входные данные
На вход программы поступает строка, которая содержит только латинские буквы, длина строки не превышает 50000 символов.

Выходные данные
Требуется вывести одно число – ответ на вопрос задачи.


Решается с помощью хешей на строках: http://e-maxx.ru/algo/string_hashes

Моё ешение:

код: [ скачать ] [ спрятать ]
Используется синтаксис C++
bool substring_eq(const vector<uint64_t> &p_pow, const vector<uint64_t> &h,
                   size_t i1, size_t i2, size_t len) {
     uint64_t h1 = h[i1 + len - 1];
     if (i1) h1 -= h[i1 - 1];
     uint64_t h2 = h[i2 + len - 1];
     if (i2) h2 -= h[i2 - 1];

     return (i1 < i2 && (h1 * p_pow[i2 - i1]) == h2) ||
            (i1 > i2 && h1 == (h2 * p_pow[i1 - i2]));
 }

 void compute_hashes(const string &s, vector<uint64_t> &p_pow, vector<uint64_t> &h) {
     const int p = 191;
     p_pow[0] = 1;
     for (size_t i = 1; i < p_pow.size(); ++i) {
         p_pow[i] = p_pow[i - 1] * p;
     }

     for (size_t i = 0; i < s.length(); ++i) {
         h[i] = (s[i] - 'A' + 1) * p_pow[i];
         if (i) h[i] += h[i - 1];
     }
 }

 size_t solve(const string &s) {
     vector<uint64_t> p_pow(s.length()), hashes(s.length());

     compute_hashes(s, p_pow, hashes);

     size_t cycle_len = s.length();
     for (size_t k = 1; k < s.length(); ++k) {
         if (substring_eq(p_pow, hashes, 0, k, s.length() - k)) {
             cycle_len = k;
             break;
         }
     }
     return cycle_len;
 }

 int main() {
     //test();

     string input;
     cin >> input;
     cout << solve(input) << std::endl;
     return 0;
 }
 


Валится последний тест (неверный ответ).

Написал генератор строк, который ничего не поймал:

код: [ скачать ] [ спрятать ]
Используется синтаксис C++
 //////////////////////////
 /// Stress testing
 //////////////////////////
 #include <random>

 std::string random_string(std::string::size_type length) {
     static auto &chrs = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

     static std::mt19937 rg{std::random_device{}()};
     static std::uniform_int_distribution<std::string::size_type> pick(0, sizeof(chrs) - 2);

     std::string s;

     s.reserve(length);

     while (s.length() < length) {
         char ch = chrs[pick(rg)];
         if (s.find(ch) == string::npos) {
             s += ch;
         }
     }

     return s;
 }

 size_t solve(const string &s);
 void test() {
     srand(100);
 #pragma clang diagnostic push
 #pragma clang diagnostic ignored "-Wmissing-noreturn"
     while (true) {
         string::size_type len = (unsigned long) (rand() % 50 + 1);
         string s = random_string(len);
         int count = rand() % 5000 + 2;
         string input;
         for (int i = 0; i < count; ++i) {
             input += s;
         }
         string input1 = input;
         input1 = input1.substr(rand() % (input1.length() - s.length()));
         input1 = input1.substr(0, rand() % (input1.length() - s.length()) + s.length());

         if (input1.empty()) continue;

         size_t k = solve(input1);
         if (k != s.length()) {
             cout << "boom:" << input1;
         }
     }
 #pragma clang diagnostic pop
 }
 //////////////////////////


Пожалуйста, помогите найти ошибку в решении.

 Профиль  
                  
 
 Re: Циклическая строка
Сообщение11.01.2017, 12:09 


22/12/08
17
Санкт-Петербург
Против хешей по модулю степени двойки есть универсальный тест - строка Туэ-Морса. Подробнее на Codeforces.

Сама же задача решается при помощи префикс-функции или Z-функции. Чтобы придумать это решение, помогает выписать одну из этих последовательностей для нескольких строк и внимательно на неё посмотреть. Реализация получается очень короткая.

 Профиль  
                  
 
 Re: Циклическая строка
Сообщение20.01.2017, 21:53 


07/03/13
22
Причина была именно в этом. Спасибо.

Если нужна корректная реализация хешей, то здесь http://codeforces.com/blog/entry/17507 проверено, что всё работает.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Toucan, maxal, Karan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group