Editorial for strpow: Lũy thừa của chuỗi

Hiểu bài toán

Bài toán yêu cầu kiểm tra xem một xâu T có phải là xâu lũy thừa bậc K của xâu S hay không. Xâu lũy thừa bậc K của S là xâu được tạo ra bằng cách nối S với chính nó K lần liên tiếp. Ví dụ, nếu S = "abc" và K = 3 thì xâu lũy thừa là "abcabcabc". Input gồm S, T, K. Output là YES nếu T là xâu lũy thừa bậc K của S, ngược lại in NO.

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

Cách Construct and Compare (Xây dựng và So sánh)

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

int main() {
    char s[1001], t[100001], k;
    scanf("%s %s %d", s, t, &k);

    char constructed[100001] = "";
    for (int i = 0; i < k; i++) {
        strcat(constructed, s);
    }

    if (strcmp(constructed, t) == 0) {
        printf("YES");
    } else {
        printf("NO");
    }
    return 0;
}

• Time Complexity: O(|S| * K)
• Space Complexity: O(|S| * K)

Phương pháp này kiểm tra độ dài trước, sau đó tạo ra một xâu mới bằng cách nối xâu S K lần, rồi so sánh xâu mới tạo này với xâu T. Nếu chúng giống nhau thì in YES, ngược lại in NO. Cách này đơn giản và dễ hiểu nhưng tốn bộ nhớ và thời gian để xây dựng xâu.

Cách Direct Verification (Kiểm tra Trực tiếp)

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

int main() {
    char s[1001], t[100001];
    int k;
    scanf("%s %s %d", s, t, &k);

    int len_s = strlen(s);
    int len_t = strlen(t);

    if (len_t != len_s * k) {
        printf("NO");
        return 0;
    }

    int check = 1;
    for (int i = 0; i < len_t; i++) {
        if (t[i] != s[i % len_s]) {
            check = 0;
            break;
        }
    }

    if (check) printf("YES");
    else printf("NO");

    return 0;
}

• Time Complexity: O(|T|)
• Space Complexity: O(1)

Đây là cách tối ưu nhất. Thay vì xây dựng xâu lũy thừa, ta chỉ cần kiểm tra từng ký tự của T. Nếu độ dài T không bằng |S| * K, đáp án là NO ngay. Nếu độ dài hợp lệ, ta duyệt qua T, với mỗi vị trí i, ký tự T[i] phải trùng với ký tự S tại vị trí i % |S|. Nếu tất cả đều khớp, in YES.

Cách Kraft’s Approach (Simulating Array)

#include <stdio.h>
#include <string.h>
int main() {
    char s[1001];
    char s_1[1001];
    int k;
    scanf("%s %s %d", &s, &s_1, &k);
    int len_s = strlen(s);
    int len_bd = len_s;
    int index = len_s;
    for(int i = 0; i < k - 1; i++) {
        for(int j = 0; j < len_bd; j++) {
            s[index] = s[j];
            ++index;
        }
    }
    int check = 1;
    for(int i = 0; i < strlen(s_1); i++) {
        if(s_1[i] != s[i]) {
            check = 0;
            break;
        }
    }
    if(check) printf("YES");
    else printf("NO");
    return 0;
}

• Time Complexity: O(|S| * K)
• Space Complexity: O(|S| * K)

Cách này tương tự cách 1 nhưng thực hiện việc nối xâu trực tiếp vào mảng bộ nhớ của xâu S ban đầu (nếu bộ nhớ cho phép). Nó sửa đổi mảng S để chứa xâu lũy thừa và so sánh. Tuy nhiên, về bản chất vẫn tốn thời gian và bộ nhớ tương đương cách 1.

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

Bài học kinh nghiệm

• Kiểm tra độ dài của T trước tiên: strlen(T) phải bằng strlen(S) * K. Nếu không, kết quả chắc chắn là NO.
• So sánh từng ký tự thay vì tạo xâu mới giúp tiết kiệm bộ nhớ và thời gian.
• Công thức kiểm tra ký tự: T[i] phải bằng S[i % len_S].

Lỗi thường gặp

• Quên kiểm tra độ dài của T trước khi so sánh nội dung.
• Sử dụng mảng có kích thước quá nhỏ cho xâu T (|T| có thể lên tới 10^6 nếu |S|=1000, K=1000).
• Lỗi tràn bộ nhớ khi cố gắng tạo xâu lũy thừa đầy đủ trong bộ nhớ stack.