Editorial for jewels: Chuỗi ngọc

Hiểu bài toán

Bài toán yêu cầu kiểm tra xem mỗi chuỗi $Si$ có phải là một phần của chuỗi vòng (circular string) $S$ hay không. Cụ thể, chuỗi $S$ được xem như một vòng tròn các ký tự, và $Si$ được cắt ra từ vòng tròn này theo một hướng nhất định (thuận hoặc ngược?). Dựa vào các giải pháp và ví dụ, ta thấy: $S$ là 'abcde'. 'abcde' (YES), 'bcdea' (YES), 'cbaed' (NO), 'cdeab' (YES). Các chuỗi YES đều là các xâu liên tiếp theo chiều kim đồng hồ của $S$. 'cbaed' là xâu nghịch đảo (hoặc không theo thứ tự) nên là NO. Như vậy, bài toán chỉ cần kiểm tra xem $Si$ có phải là một rotation (xoay vòng) của $S$ hay không. Nếu $Si$ có độ dài khác $S$ thì chắc chắn NO. Nếu bằng thì ta ghép $S$ với chính nó thành $SS$, nếu $Si$ là xâu con của $SS$ thì $Si$ là một rotation của $S$.

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

Cách Sử dụng hàm Find (strstr)

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

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    char s[100005];
    scanf("%s", s);
    char ss[200005];
    strcpy(ss, s);
    strcat(ss, s); // Tạo xâu SS
    while (k--) {
        char t[100005];
        scanf("%s", t);
        // Kiểm tra t có phải là xâu con của SS không
        if (strstr(ss, t) != NULL) 
            printf("YES\n");
        else 
            printf("NO\n");
    }
    return 0;
}

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

Đây là cách tiếp cận trực quan nhất. Ta tạo ra một xâu $SS$ bằng cách nối $S$ với chính nó. Nếu $Si$ là một rotation của $S$, thì $Si$ chắc chắn sẽ xuất hiện liên tiếp trong $SS$. Ví dụ: $S = \text{'abcde'}$, $SS = \text{'abcdeabcde'}$. Xâu 'cdeab' nằm trong $SS$. Ta chỉ cần dùng hàm strstr (tìm xâu con) có sẵn trong thư viện string.h của C hoặc find trong C++. Độ phức tạp phụ thuộc vào hàm thư viện, thường là $O(N \cdot M)$, nhưng với $N$ nhỏ (<= 10^5) và $K$ nhỏ (<= 10), phương pháp này chạy rất nhanh.

Cách Quay lui (Backtracking)

// Pseudocode cho Backtracking (Không hiệu quả)
bool check(string S, string target) {
    if (S.length() != target.length()) return false;
    // Thử từng vị trí bắt đầu trong S
    for (int i = 0; i < S.length(); i++) {
        bool match = true;
        for (int j = 0; j < target.length(); j++) {
            if (S[(i + j) % S.length()] != target[j]) {
                match = false;
                break;
            }
        }
        if (match) return true;
    }
    return false;
}

• Time Complexity: O(N^2 * K)
• Space Complexity: O(1)

Phương pháp này kiểm tra từng ký tự của $S_i$ với $S$ bằng cách duyệt qua từng vị trí bắt đầu có thể trong $S$. Nếu độ dài $N$ lên tới $10^5$, độ phức tạp $O(N^2)$ sẽ dẫn đến Time Limit Exceeded (TLE). Đây là phương pháp brute-force cơ bản, chỉ phù hợp với dữ liệu nhỏ. Trong các giải pháp nộp bài thực tế, người ta thường không dùng cách này do độ phức tạp cao.

Cách Rabin-Karp (String Hashing)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

const int BASE = 31;
const int MOD = 1e9 + 7;

int main() {
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;

    // Tính hash cho SS (S + S)
    string SS = S + S;
    int L = SS.length();
    vector<long long> hash(L + 1, 0);
    vector<long long> pow(L + 1, 1);

    for (int i = 0; i < L; i++) {
        hash[i+1] = (hash[i] * BASE + (SS[i] - 'a' + 1)) % MOD;
        pow[i+1] = (pow[i] * BASE) % MOD;
    }

    while (K--) {
        string T;
        cin >> T;
        if (T.length() != N) {
            cout << "NO\n";
            continue;
        }
        // Tính hash của T
        long long hashT = 0;
        for (char c : T) {
            hashT = (hashT * BASE + (c - 'a' + 1)) % MOD;
        }

        bool found = false;
        // Kiểm tra các vị trí trong SS (từ 0 đến N-1)
        for (int i = 0; i < N; i++) {
            // Hash từ i đến i+N-1 trong SS
            long long h = (hash[i+N] - hash[i] * pow[N] % MOD + MOD) % MOD;
            if (h == hashT) {
                found = true;
                break;
            }
        }
        cout << (found ? "YES" : "NO") << "\n";
    }
    return 0;
}

• Time Complexity: O(N + K * N)
• Space Complexity: O(N)

Đây là phương pháp tối ưu hơn cho các giới hạn lớn. Thay vì so sánh ký tự trực tiếp, ta sử dụng Rolling Hash. Ta tính toán giá trị số học của các xâu con. Nếu giá trị hash của $S_i$ khớp với giá trị hash của một xâu con độ dài $N$ trong $SS$, thì chúng có khả năng khớp nhau (và với MOD lớn, xác suất đụng độ rất thấp). Phương pháp này giúp giảm độ phức tạp thời gian so với việc dùng strstr hoặc so sánh trực tiếp từng ký tự, mặc dù trong bài này do $K$ nhỏ nên strstr cũng đủ.

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

Bài học kinh nghiệm

• Bài toán quy về kiểm tra xem $S_i$ có phải là 'rotation' của $S$ hay không.
• Mẹo kinh điển: Ghép $S$ với chính nó ($S + S$). Nếu $Si$ là rotation của $S$ thì $Si$ là xâu con của $S + S$.
• Với ràng buộc $N \le 10^5$ và $K \le 10$, thư viện strstr của C hoặc string::find của C++ là đủ mạnh và là lựa chọn đơn giản nhất.

Lỗi thường gặp

• Quên kiểm tra độ dài: Nếu $S_i$ có độ dài khác $S$ thì chắc chắn không phải là rotation (trừ khi bài toán định nghĩa khác, nhưng ở đây là 'cắt ra từ vòng ngọc giống với mẫu' nên độ dài phải bằng).
• Lỗi truy cập mảng: Khi dùng mảng tĩnh C, cần đảm bảo mảng dung tích đủ chứa $S + S$ (tức là $2N$).
• Sử dụng thuật toán quá phức tạp không cần thiết (như KMP) trong khi strstr hoặc find đã giải quyết được vấn đề trong giới hạn đề bài.