Приветствую.
Есть такая задача:
http://informatics.mccme.ru/mod/stateme ... id=12475#1Цитата:
Строка S была записана много раз подряд, после чего из получившейся строки взяли подстроку и дали вам. Ваша задача определить минимально возможную длину исходной строки S.
Входные данные
На вход программы поступает строка, которая содержит только латинские буквы, длина строки не превышает 50000 символов.
Выходные данные
Требуется вывести одно число – ответ на вопрос задачи.
Решается с помощью хешей на строках:
http://e-maxx.ru/algo/string_hashes Моё ешение:
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;
}
Валится последний тест (неверный ответ).
Написал генератор строк, который ничего не поймал:
//////////////////////////
/// 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
}
//////////////////////////
Пожалуйста, помогите найти ошибку в решении.
