459. Kiểm tra chuỗi có thể được tạo thành từ việc lặp lại một chuỗi con

Mô tả bài toán:
Cho một chuỗi ký tự s, xác định xem liệu nó có thể được biểu diễn dưới dạng việc lặp lại một chuỗi con không rỗng nhiều lần (ít nhất hai lần). Ví dụ: "abab" → true ("ab" lặp 2 lần), trong khi "aba" → false.

Giải pháp 1: Sử dụng mảng prefix function (KMP)

Tư tưởng chính:
Nếu chuỗi s có dạng t + t + ... + t (k ≥ 2 lần), thì phần tiền tố dài nhất trùng với hậu tố (longest proper prefix which is also suffix – LPS) sẽ có độ dài bằng n − |t|. Do đó, nếu gọi lps[n−1] là giá trị cuối cùng của mảng LPS, thì n % (n − lps[n−1]) == 0 và lps[n−1] > 0 là điều kiện đủ để kết luận chuỗi có cấu trúc lặp.

Lưu ý: Trong cài đặt sau, mảng lps được xây dựng theo chuẩn KMP (không dùng kỹ thuật "−1 offset" như một số tài liệu cổ), giúp dễ hiểu hơn về ngữ nghĩa chiều dài tiền tố – hậu tố chung.

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.length();
        if (n < 2) return false;

        // Xây dựng mảng LPS: lps[i] = độ dài tiền tố dài nhất của s[0..i]
        // đồng thời là hậu tố của s[0..i], khác toàn bộ s[0..i]
        vector<int> lps(n, 0);
        int len = 0; // độ dài tiền tố khớp hiện tại
        int i = 1;
        while (i < n) {
            if (s[i] == s[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }

        int longest_suffix_prefix = lps[n - 1];
        // Nếu tồn tại tiền-hậu tố chung và độ dài chuỗi chia hết cho chu kỳ tiềm năng
        return (longest_suffix_prefix > 0 && n % (n - longest_suffix_prefix) == 0);
    }
};

Giải pháp 2: Phương pháp nối chuỗi (string doubling trick)

Tư tưởng chính:
Nếu s = t^k với k ≥ 2, thì s + s chứa ít nhất ba bản sao của t. Khi loại bỏ ký tự đầu và ký tự cuối của s + s, chuỗi mới vẫn phải chứa trọn vẹn s như một chuỗi con — vì s nằm hoàn toàn bên trong phần giao nhau giữa hai bản sao.

Ví dụ:
s = "abab" → s+s = "abababab" → cắt đầu/cuối → "bababa" → "abab" xuất hiện tại vị trí thứ 1.

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string doubled = s + s;
        // Loại bỏ ký tự đầu và ký tự cuối
        doubled = doubled.substr(1, doubled.length() - 2);
        // Kiểm tra xem s có xuất hiện trong doubled hay không
        return doubled.find(s) != string::npos;
    }
};

Giải pháp 3: Duyệt từng độ dài chuỗi con tiềm năng

Tư tưởng chính:
Thử mọi độ dài len từ 1 đến n / 2. Với mỗi len, kiểm tra xem s[0..len−1] có phải là "khối nền" hay không bằng cách so sánh từng đoạn s[i*len .. (i+1)*len − 1] với khối nền.

Tối ưu: Bỏ qua các len không là ước của n, vì nếu chuỗi con lặp được thì độ dài toàn bộ phải chia hết cho độ dài khối.

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        for (int block_len = 1; block_len <= n / 2; ++block_len) {
            if (n % block_len != 0) continue;

            string base = s.substr(0, block_len);
            bool valid = true;
            for (int i = 1; i < n / block_len; ++i) {
                string segment = s.substr(i * block_len, block_len);
                if (segment != base) {
                    valid = false;
                    break;
                }
            }
            if (valid) return true;
        }
        return false;
    }
};