there is a knows problem stated as "Cyclic string":
A string S has been recorded many times, and then from the resulting line took a substring, and give to you.Your task is to determine the minimum possible length of a string S.
Input
In the first and only line of the input file contains a string that contains only letters, line length up to 50000 characters.
Output
The output file you want to display a single number - the answer to the problem.
It can be solved with substring hashes (source).
I composed a solution:
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;
}
I can't passed the last test in e-judging system (I don't know the contents of it).
I even composed a function that generates input strings, but it catches no errors:
//////////////////////////
/// 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
}
//////////////////////////
What else did I miss in the solution?