Editorial for compress: Nén xâu

Hiểu bài toán

Bài toán yêu cầu nén một xâu S đã cho. Xâu nén được tạo thành bằng cách chọn một xâu T ngắn nhất sao cho S là kết quả của việc lặp lại T K lần (K là số nguyên dương). Xâu nén cuối cùng là chuỗi chứa K theo sau bởi xâu T. Ví dụ: S = 'abcabc' thì T = 'abc', K = 2, xâu nén là '2abc'. Nếu không tìm được xâu lặp nào khác ngoài chính nó (K=1), xâu nén là '1' + S.

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

Cách Brute Force

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

bool isRepeated(char *s, int n, int len) {
    if (n % len != 0) return false;
    for (int i = len; i < n; i++) {
        if (s[i] != s[i % len]) return false;
    }
    return true;
}

void nenxau(char a[], int n) {
    for (int len = 1; len <= n / 2; len++) {
        if (isRepeated(a, n, len)) {
            printf("%d", n / len);
            for (int i = 0; i < len; i++) putchar(a[i]);
            return;
        }
    }
    printf("1%s", a);
}

int main() {
    char a[10000];
    fgets(a, sizeof(a), stdin);
    a[strcspn(a, "\n")] = '\0';
    int n = strlen(a);
    nenxau(a, n);
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Phương pháp này duyệt qua tất cả các độ dài 'len' có thể của xâu lặp (từ 1 đến n/2). Với mỗi độ dài 'len', nó kiểm tra xem xâu S có phải là sự lặp lại của xâu con đầu tiên có độ dài 'len' hay không. Việc kiểm tra được thực hiện bằng cách so sánh từng ký tự của S với ký tự tương ứng trong xâu con cơ bản (dựa trên phép chia lấy dư chỉ số). Nếu tìm thấy một xâu lặp, ta in ra số lần lặp và xâu con đó rồi kết thúc. Nếu duyệt hết mà không tìm thấy, in ra '1' và xâu S ban đầu.

Cách Optimized Brute Force

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

int check(char *s, char *e, int k) {
    int ns = strlen(s);
    int ne = strlen(e);
    if (ns != ne * k) return 0;
    for (int i = 0; i < ns; i++) {
        if (s[i] != e[i % ne]) return 0;
    }
    return 1;
}

void nenxau(char *s) {
    int len_s = strlen(s);
    for (int i = 1; i <= len_s; i++) {
        if (len_s % i == 0) {
            int k = len_s / i;
            char tmp[i + 1];
            strncpy(tmp, s, i);
            tmp[i] = '\0';
            if (check(s, tmp, k)) {
                printf("%d%s", k, tmp);
                return;
            }
        }
    }
    printf("1%s", s);
}

int main() {
    char s[1003];
    scanf("%s", s);
    nenxau(s);
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Đây là biến thể của phương pháp Brute Force. Thay vì chỉ kiểm tra điều kiện chia hết độ dài và so sánh trực tiếp trong một hàm, phương pháp này tạo một bản sao tạm thời (tmp) của xâu con đầu tiên độ dài i. Sau đó gọi một hàm kiểm tra riêng để đảm bảo tmp lặp lại K lần tạo thành S. Logic cơ bản tương tự, độ phức tạp vẫn là O(n^2) do lặp qua các độ dài và kiểm tra lại toàn bộ xâu.

Cách KMP Algorithm (String Periodicity)

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

#define MAX 1005

int pi[MAX];
char S[MAX];

// Tính mảng tiền tố (prefix function) của KMP
void computePrefixFunction(int n) {
    pi[0] = 0;
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && S[i] != S[j])
            j = pi[j - 1];
        if (S[i] == S[j])
            j++;
        pi[i] = j;
    }
}

int main() {
    scanf("%s", S);
    int n = strlen(S);

    computePrefixFunction(n);

    // Độ dài của xâu lặp cơ bản là len = n - pi[n-1]
    int len = n - pi[n - 1];

    // Kiểm tra xem n có chia hết cho len không
    if (n % len == 0) {
        printf("%d%.*s\n", n / len, len, S);
    } else {
        printf("1%s\n", S);
    }

    return 0;
}

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

Đây là cách tiếp cận tối ưu nhất dựa trên lý thuyết xâu. Ta sử dụng thuật toán KMP để tính mảng tiền tố (pi). Nếu xâu S có độ dài chu kỳ (period) là p, thì pi[n-1] (giá trị tiền tố dài nhất khớp với hậu tố) sẽ bằng n - p. Do đó, độ dài của xâu lặp cơ bản (T) là p = n - pi[n-1]. Ta chỉ cần kiểm tra xem n có chia hết cho p không. Nếu có, S là một xâu lặp và xâu nén là (n/p) + T. Nếu không, S không phải là xâu lặp của bất kỳ xâu con nào khác (trừ chính nó), in ra 1 + S.

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

Bài học kinh nghiệm

• Xâu S là sự lặp lại của một xâu con T độ dài len nếu và chỉ nếu len là ước của |S| và mọi ký tự S[i] đều bằng S[i % len].
• Với ràng buộc độ dài xâu |S| <= 1000, giải thuật O(n^2) (Brute Force) là hoàn toàn khả thi và dễ cài đặt.
• Thuật toán KMP cho phép tìm xâu lặp cơ bản trong thời gian tuyến tính O(n) bằng cách tính mảng tiền tố.

Lỗi thường gặp

• Quên kiểm tra xem độ dài xâu S có chia hết cho độ dài xâu con候选 (candidate) hay không.
• Xử lý sai trường hợp K=1 (không tìm thấy xâu lặp nào).
• Lỗi truy cập bộ nhớ khi tạo xâu tạm trong vòng lặp.