Bình luận

• 
  

  1

  SPyofgame    2:20 p.m. 15 Tháng 6, 2020 ← đã chỉnh sửa →

  ---

  Spoiler Alert

  ---

  Hint 1

  • Nếu xâu có chu kì \(T\) thì độ dài xâu con là \(T * subsize = size(S)\)

  Từ đây \(\Rightarrow\) ta chỉ xét các vị trí mà tồn tại \(T\) để \(T \times subsize_{current} = size(S)\)

  ---

  Hint 2

  • Xét bài toán con bé, kiểm tra xem xâu con \(sub\) có xuất hiện kề nhau trong xâu \(S\) đủ \(T\) lần không

  Ta sẽ kiểm tra các xâu con độ dài \(subsize\) liên tiếp trong xâu \(S\)

  Nếu chỉ cần một kí tự khác thì ta loạyêui bỏ trường hợp \(sub\) ngay

  Đề yêu cầu xâu xuất ra phải nhỏ nhất, nên xâu có chu kì càng lớn, độ dài càng nhỏ thì mình chọn

  ---

  Reference AC code | \(O(?) \leq O(n ^ 2)\) time | \(O(n)\) auxiliary space | String

  C++

  int main()
  {
      /// Nhan xau
      string s;
      cin >> s;
  
      string sub;
      for (int i = 0; i < s.size(); ++i)
      {
          sub += s[i];
          if (s.size() % sub.size() != 0) continue; /// Neu no khong co chu ki (T)
  
          bool ok = true;
          for (int j = sub.size(); j < s.size(); j += sub.size())
              if (s.substr(j, sub.size()) != sub) /// Duyet qua cac xau ke nhau do dai (subsize)
                  { ok = false; break; }
  
          if (ok == true) /// Neu tim duoc xau con thoa man
               return cout << (s.size() / sub.size()) << sub, 0; /// Chu ki (T) = s.size() / subsize
      }
      return 0;
  }
  

  Hint 3

  • Có \(n\) chia hết cho \(a\) thì \(n\) cũng chia hết cho \(n / a\)

  Từ tiếp cận này ta có thể xét và kiểm tra với 2 độ dài là \(subsize\) và \(S.size() / subsize\)

  • \(a \times b = n\) và \(0 \leq a \leq b\) thì \(a \leq \sqrt n\)

  Từ nhận xét này ta chỉ cần duyệt tới \(\sqrt n\)

  ---

  Hint 4

  • Đề yêu cầu kiếm xâu rút gọn nhỏ nhất

  Nếu xâu sub độ dài \(subsize\) thỏa mãn thì xuất ngay

  Nếu xâu sub độ dài \(S.size() / subsize\) thỏa mãn thì mình chỉ lấy giá trị bé nhất, mà \(S.size() / subsize\) càng bé khi \(subsize\) càng lớn nên mình không xuất ra ngay được

  ---

  Reference AC code | \(O(n \sqrt n)\) time | \(O(n)\) auxiliary space |

  C++

  int n;
  string s, pat;
  inline bool check(int subsize) { /// Ham kiem tra
      pat = s.substr(0, subsize);
      for (int head = subsize; head < n; head += subsize) /// Duyet qua cac xau con ke nhau do dai (subsize)
          for (int pos = 0; pos < subsize; ++pos) /// Duyet qua tung vi tri de so sanh voi xau (sub)
               if (pat[pos] != s[head + pos]) /// Neu 2 ki tu khac nhau thi xau khong co chu ki (T)
                  return false; /// Loai
  
      return true; /// Nhan
  }
  
  int main() {
      /// Nhan xau
      cin >> s;
      n = s.size();
  
      int sqrtn = sqrt(n);
      int res = 0;
      for (int subsize = 1; subsize <= sqrtn; ++subsize) { /// Duyet qua tung do dai khong qua sqrtn
          if (n % subsize != 0) continue;                           /// Neu khong co chu ki (T) thi loai
          if (check(subsize)) return cout << n / subsize << pat, 0; /// Co chu ki (T) do dai (n / subsize)
          if (check(n / subsize)) res = subsize;                    /// Chon gia tri nho nhat
      }
  
      cout << res << s.substr(0, n / res); /// Trong truong hop con lai
  }
  

  Another Approach

  • Optimize từ thuật trên

  ---

  Reference AC code | \(O(n \sqrt n)\) time | \(O(n)\) auxiliary space | String

  C++

  int n;
  string s, sub;
  inline bool check(int subsize) {
      for (int head = subsize; head < n; head += subsize)
          for (int pos = 0; pos < subsize; ++pos)
              if (sub[pos] != s[head + pos])
                  return false;
  
      cout << n / subsize << sub;
      exit(0);
  }
  
  int main() {
      cin >> s;
      n = s.size();
  
      vector<int> upper_divisors;
      int sqrtn = sqrt(n);
      for (int subsize = 1; subsize <= sqrtn; ++subsize) {
          sub += s[subsize - 1];
          if (n % subsize == 0) {
              upper_divisors.push_back(n / subsize);
              check(subsize);
          }
      }
  
      reverse(all(upper_divisors));
      for (int subsize : upper_divisors) {
          while (sub.size() < subsize) sub.push_back(s[sub.size()]);
          check(subsize);
      }
  }
  

  Question

  • Liệu bài này có thể giải bằng cách khác nhanh hơn không ?
• 
  

  -2

  hoangvind    3:00 p.m. 23 Tháng 8, 2024

  code màu mè thế
5 bình luận nữa