Hiểu bài toán

Xác định xem một xâu ký tự S có phải là 'xâu kép' hay không. Xâu kép được định nghĩa là một xâu có thể được tạo thành bằng cách lặp lại chính xác hai lần một xâu con khác. Ví dụ: 'abab' là xâu kép ('ab' lặp 2 lần), 'abcabc' cũng là xâu kép ('abc' lặp 2 lần). Ngược lại, 'ababa' không phải là xâu kép.

Formal: Cho xâu S độ dài N. Tìm xem có tồn tại một xâu con A sao cho S = A + A (nối hai xâu A lại với nhau) hay không.

Các cách tiếp cận

Cách Chia đôi và kiểm tra (Naive)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ifstream fin("DUPSTR.inp");
    ofstream fout("DUPSTR.out");

    string s;
    fin >> s;

    int n = s.size();
    if(n % 2 != 0) {
        fout << "No\n";
    } else {
        string first = s.substr(0, n/2);
        string second = s.substr(n/2, n/2);
        if(first == second) fout << "Yes\n";
        else fout << "No\n";
    }

    fin.close();
    fout.close();
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là cách tiếp cận trực quan nhất. Xâu kép phải có độ dài chẵn, nên nếu độ dài N là số lẻ, đáp án chắc chắn là 'No'. Nếu N chẵn, ta chia xâu thành hai nửa bằng nhau. Nếu nửa đầu tiên giống hệt nửa thứ hai, thì xâu đó là xâu kép.

Cách thực hiện:

1. Kiểm tra tính chẵn lẻ của N.
2. Tạo xâu first chứa N/2 ký tự đầu.
3. Tạo xâu second chứa N/2 ký tự cuối.
4. So sánh first và second.

Ưu điểm: Dễ hiểu, dễ code. Nhược điểm: Phải tạo xâu con mới (tốn bộ nhớ) và so sánh từng ký tự.

Cách Kiểm tra trực tiếp từng ký tự

#include <bits/stdc++.h>
using namespace std;

int main() {
    ifstream fin("DUPSTR.inp");
    ofstream fout("DUPSTR.out");

    string s;
    fin >> s;
    int n = s.size();

    // Kiểm tra độ dài chẵn
    if (n % 2 != 0) {
        fout << "No";
        return 0;
    }

    int half = n / 2;
    bool is_duplicate = true;
    // Kiểm tra từng ký tự xem có khớp với ký tự tương ứng ở nửa sau không
    for (int i = 0; i < half; ++i) {
        if (s[i] != s[i + half]) {
            is_duplicate = false;
            break;
        }
    }

    if (is_duplicate) fout << "Yes";
    else fout << "No";

    fin.close();
    fout.close();
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Tiếp cận này tối ưu hơn so với việc tạo xâu con.

Cách thực hiện:

1. Kiểm tra N chẵn.
2. Duyệt từ chỉ số 0 đến N/2 - 1.
3. So sánh trực tiếp s[i] và s[i + N/2].
4. Nếu có bất kỳ cặp ký tự nào không khớp, lập tức dừng và trả về 'No'.

Ưu điểm: Tiết kiệm bộ nhớ (không tạo xâu con), độ phức tạp thời gian tốt. Nhược điểm: Code hơi dài dòng hơn một chút.

Cách Quét divisors (Tối ưu)

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    freopen("DUPSTR.inp","r",stdin);
    freopen("DUPSTR.out","w",stdout);
    string s;
    cin>>s;
    int n=s.size();
    bool ok=false;
    // Chỉ kiểm tra các ước của n (bỏ qua ước bằng n vì cần lặp 2 lần)
    for(int i=1;i*i<=n;++i){
        if(n%i==0){
            // i là ước của n
            int j = n/i;
            // Kiểm tra nếu j=2 (tức là i = n/2)
            if(j == 2) {
                string x=s.substr(0, i);
                string ans = x + x;
                if(ans==s) { ok=true; break; }
            }
            // Kiểm tra nếu i=2 (tức là j = n/2)
            if(i == 2 && i != j) {
                int k=n/i;
                string x=s.substr(0, k);
                string ans = x + x;
                if(ans==s) { ok=true; break; }
            }
        }
    }
    cout<<(ok?"Yes":"No");
    return 0;
}

• Time Complexity: O(sqrt(N) * N)
• Space Complexity: O(N)

Solution 1 (GodOfSever) sử dụng một kỹ thuật khá lạ lẫm cho bài toán này. Nó duyệt qua tất cả các ước của độ dài N.

Logic:

• Xâu kép S có độ dài N được tạo bởi A lặp 2 lần (S = A + A). Độ dài A là N/2.
• Do đó, độ dài N của S phải chia hết cho 2.
• Solution này duyệt qua các ước i của N. Nó tìm cách chia N thành 2 phần.
• Nếu n % i == 0, nó thử lấy xâu con độ dài i làm đơn vị lặp.
• Nó tạo ans = x + x và so sánh với s.
• Logic if(i!=n/i) và các điều kiện bên trong của code này hơi rườm rà và không chuẩn hóa cho bài toán "lặp 2 lần". Nó dường như đang kiểm tra xem có thể chia xâu thành các phần lặp lại hay không (không nhất thiết là 2 lần).
• Tuy nhiên, với yêu cầu bài toán là "lặp 2 lần", cách tiếp cận này quá mức cần thiết và phức tạp hóa vấn đề.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Đặc điểm quan trọng nhất của xâu kép (lặp 2 lần) là độ dài của nó phải là số chẵn.
• Nếu biết độ dài xâu con lặp (k), ta chỉ cần so sánh ký tự tại vị trí i với vị trí i + k.
• Với bài toán chỉ kiểm tra lặp đúng 2 lần, ta chỉ cần kiểm tra trường hợp độ dài xâu con bằng N/2.

Lỗi thường gặp

• Quên kiểm tra độ dài xâu có chẵn hay không trước khi chia đôi.
• Sử dụng substr tạo ra các xâu tạm thời làm tăng độ phức tạp bộ nhớ không cần thiết.
• Lầm tưởng rằng bài toán yêu cầu tìm mọi độ dài lặp có thể (như Solution 1 đang làm), trong khi đề bài chỉ hỏi về "xâu kép" (lặp 2 lần).