Rút gọn xâu

Xem PDF

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Cho một xâu \(S\) chỉ gồm các chữ cái in thường. Cách mô tả rút gọn của xâu \(S\) như sau:

  • Chọn ra một xâu \(X\) ngắn nhất có thể và một số nguyên dương \(K\), sao cho khi viết xâu \(X\) lặp lại \(K\) lần thì ta thu được xâu \(S\)
  • Ghép \(K\)\(X\), ta thu được xâu rút gọn của \(S\).

Ví dụ:

  • Xâu rút gọn của “abababab” là “4ab”
  • Xâu rút gọn của “aaa” là “3a”
  • Xâu rút gọn của “abac” là “1abac”

Input

  • Gồm một dòng duy nhất chứa xâu \(S\) có độ dài không quá \(1000\).

Output

  • In ra xâu rút gọn của xâu \(S\).

Example

Test 1

Input
abababab 
Output
4ab

Test 2

Input
aaa 
Output
3a

Test 3

Input
abac 
Output
1abac

Bình luận


  • -2
    NgJaBach 8:54 p.m. 26 Tháng 8, 2020

    dùng KMP được không nhỉ


    • 2
      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

      • \(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\)\(S.size() / subsize\)

      • \(a \times b = n\)\(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 ?