Rút gọn xâu

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
admin
Dạng bài
Đ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\) và \(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


  • -6
    soclun1313    8:50 p.m. 24 Tháng 6, 2024

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


    • -6
      soclun1313    8:48 p.m. 24 Tháng 6, 2024

      Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


      • 2
        baothanh2010    8:39 a.m. 6 Tháng 6, 2024

        include <bits/stdc++.h>

        using namespace std;
        string s,x,y;
        long long res=0;
        int main()
        {
        cin>>s;
        res=s.size()-1;
        for(long long i=1;i<=s.size();i++)
        {
        x=s.substr(0,i);
        y=s.substr(res,i);
        res--;
        if(x==y)
        {
        cout<<s.size()/i<<x;
        return 0;
        }
        }
        return 0;
        }


        • 1
          PhamDacVietAnh_2024    3:20 p.m. 25 Tháng 4, 2024

          include <bits/stdc++.h>

          using namespace std;
          long long a,b,c,d,m,x,ma,k,q,j,f;
          string n,z,t,kq[1000000],ks[1000000];
          int main()
          {
          cin>>n;
          f=n.size()-1;
          for(long long i=1;i<=n.size();i++)
          {
          t=n.substr(0,i);
          z=n.substr(f,-i);
          f--;
          //cout<<t<<"---"<<z<<'\n';
          if(t==z) {cout<<n.size()/i<<t; break;}
          }

          }


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

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


            • 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 ?
              1 phản hồi