1
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ "I can't passed the last test in e-judging system" - is it TLE or WA? \$\endgroup\$ – vnp Dec 17 '16 at 21:07
  • \$\begingroup\$ What are TLE and WA? Particular e-judges? If yes then I don't know them. And I think it makes not a big difference where that tasks came from. \$\endgroup\$ – Alexander Myltsev Dec 17 '16 at 21:12
  • \$\begingroup\$ TLE = Time Limit Exceeded (время истекло), WA = Wrong Answer (ошибка). I am asking because WA is strictly off-topic here. \$\endgroup\$ – vnp Dec 17 '16 at 21:13
  • \$\begingroup\$ Sounds like Wrong Answer, which makes this question inappropriate for Code Review. \$\endgroup\$ – Mast Dec 17 '16 at 21:14
  • \$\begingroup\$ Welcome to Code Review! I'm afraid this question does not match what this site is about. Code Review is about improving existing, working code. Code Review is not the site to ask for help in fixing or changing what your code does. Once the code does what you want, we would love to help you do the same thing in a cleaner way! Please see our help center for more information. \$\endgroup\$ – Mast Dec 17 '16 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.