Editorial for strcmp: So sánh chuỗi

Hiểu bài toán

Cho hai số nguyên N và M trong khoảng từ 1 đến 9. Nhiệm vụ là tạo ra hai chuỗi: chuỗi thứ nhất được tạo bằng cách ghép N (dưới dạng ký tự) M lần, và chuỗi thứ hai được tạo bằng cách ghép M N lần. Sau đó, so sánh hai chuỗi này theo thứ tự từ điển và in ra chuỗi nhỏ hơn.

Ví dụ: N=3, M=4.

• Chuỗi 1: '3' ghép 4 lần -> '3333'.
• Chuỗi 2: '4' ghép 3 lần -> '444'. So sánh: '3333' < '444' theo thứ tự từ điển (vì ký tự '3' nhỏ hơn '4').

Điểm mấu chốt là so sánh từng ký tự một từ trái sang phải.

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

Cách Xây dựng chuỗi và so sánh

#include<stdio.h>
#include<string.h>

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    char a[100000],b[100000];
    sprintf(a,"%d",n);
    sprintf(b,"%d",m);
    char c[100000] = "";
    char d[100000] = "";
    for (int i = 0;i < m; i++){
        strcat(c,a);
    }
    for (int i = 0; i < n; i++){
        strcat(d,b);
    }
    if (strcmp(c,d) > 0) printf("%s",d);
    else printf("%s",c);
    return 0;
}

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

Cách tiếp cận này mô phỏng chính xác yêu cầu của đề bài.

1. Đọc N và M.
2. Chuyển N và M thành chuỗi ký tự (ví dụ sprintf).
3. Tạo chuỗi đầu tiên bằng cách lặp m lần và nối chuỗi N vào.
4. Tạo chuỗi thứ hai bằng cách lặp n lần và nối chuỗi M vào.
5. Dùng hàm strcmp để so sánh hai chuỗi kết quả và in ra chuỗi nhỏ hơn.

Cách này dễ hiểu nhưng tốn bộ nhớ và thời gian xử lý nếu N và M lớn (dù ở đây N, M chỉ tối đa 9, nên rất nhanh). Tuy nhiên, về mặt lý thuyết, độ phức tạp là O(N*M) về cả thời gian và bộ nhớ.

Cách So sánh trực tiếp (Quy tắc so sánh từ điển)

#include <stdio.h>
#include <string.h>

int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    if(a<b){
        for(int i=1;i<=b;i++){
            printf("%d",a);
        }
    }
    else {
        for(int i=1;i<=a;i++){
            printf("%d",b);
        }
    }
    return 0;
}

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

Đây là cách tiếp cận tối ưu về bộ nhớ và hiệu quả.

Luật so sánh từ điển của hai chuỗi:

1. Nếu ký tự đầu tiên khác nhau, chuỗi nào có ký tự đầu nhỏ hơn sẽ nhỏ hơn.
2. Nếu ký tự đầu giống nhau, so sánh ký tự tiếp theo, và cứ thế cho đến hết.

Phân tích:

• Chuỗi 1: 'N' lặp M lần. Ký tự đầu là N.
• Chuỗi 2: 'M' lặp N lần. Ký tự đầu là M.

Trường hợp 1: N < M Ký tự đầu tiên của chuỗi 1 là N, của chuỗi 2 là M. Vì N < M, chuỗi 1 nhỏ hơn. Ta chỉ cần in ra chuỗi 1 (N lặp lại M lần).

Trường hợp 2: N > M Ký tự đầu tiên của chuỗi 1 là N, của chuỗi 2 là M. Vì N > M, chuỗi 2 nhỏ hơn. Ta chỉ cần in ra chuỗi 2 (M lặp lại N lần).

Trường hợp 3: N == M Hai chuỗi hoàn toàn giống nhau (cùng ký tự, cùng độ dài). Ta in ra chuỗi bất kỳ.

Do đó, ta chỉ cần so sánh N và M:

• Nếu N < M: In N lặp M lần.
• Nếu N >= M: In M lặp N lần.

Cách này không cần tạo chuỗi trung gian, chỉ cần in ra kết quả trực tiếp, tối ưu hoàn toàn.

Cách Tối ưu hóa Logic (Rút gọn)

#include <stdio.h>

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    char c = (n < m) ? n + '0' : m + '0';
    int count = (n < m) ? m : n;
    for (int i = 0; i < count; i++) {
        printf("%c", c);
    }
    return 0;
}

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

Đây là biến thể của phương pháp so sánh trực tiếp, sử dụng toán tử 3 ngôi để code ngắn gọn hơn.

• Xác định ký tự cần in: Nếu n < m thì in 'n', ngược lại in 'm'.
• Xác định số lần in: Nếu n < m thì in m lần, ngược lại in n lần.
• Thực hiện vòng lặp để in ra.

Logic tương tự như phương pháp 2 nhưng code ngắn gọn hơn một chút.

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

Bài học kinh nghiệm

• Bài toán này chỉ yêu cầu so sánh thứ tự từ điển, không phải so sánh độ dài hay giá trị số học. Do đó, việc xác định ký tự đầu tiên là quan trọng nhất.
• Vì N và M là các chữ số (1-9), việc ghép chuỗi có thể được thực hiện bằng cách lặp in ký tự thay vì tạo chuỗi con.
• Giả thiết: Nếu char(N) < char(M) thì chuỗi 'N'... nhỏ hơn chuỗi 'M'... bất kể độ dài.

Lỗi thường gặp

• Quên chuyển đổi số nguyên sang ký tự trước khi so sánh hoặc in.
• Sử dụng logic so sánh số học (ví dụ: so sánh NM với MN) thay vì so sánh thứ tự từ điển.
• Tạo mảng chuỗi quá nhỏ trong khi C++/C không kiểm tra biên, dẫn đến tràn bộ nhớ (buffer overflow) nếu dùng mảng tĩnh.