Hướng dẫn cho Rút gọn xâu

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

`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 ?

Bình luận

3

NgJaBach 11:14 a.m. 22 Tháng 10, 2020

Loi giai huu ich lam!