Làm thế nào để phát hiện nhanh một chuỗi có phải là chuỗi con (Substring) nằm trong một chuỗi lớn hay không, và độ phức tạp thời gian của các phương pháp tìm kiếm cơ bản là gì?

Question

Accepted Answer

Bản chất vấn đề
Bài toán tìm kiếm chuỗi con là một trong những thao tác phổ biến nhất trong phát triển phần mềm (ví dụ: tìm kiếm từ khóa trong tài liệu, kiểm tra định dạng URL). Lập trình viên cấp độ Junior cần nắm rõ sự khác biệt về hiệu năng giữa các cách tiếp cận khác nhau.
Các phương pháp và độ phức tạp

Sử dụng hàm indexOf() hoặc includes(): Thường được cài đặt bằng các thuật toán tối ưu cấp thấp (như Two-Way hoặc Bitap) trong môi trường runtime, đạt hiệu năng rất tốt cho đa số trường hợp.
Thuật toán vét cạn (Brute Force Search): Duyệt qua từng vị trí của chuỗi lớn và so sánh từng ký tự. Độ phức tạp thời gian trong trường hợp xấu nhất là O(n * m), với n là độ dài chuỗi lớn và m là độ dài chuỗi con.

Ví dụ minh họa (JavaScript)
// Sử dụng phương thức chuẩn của ngôn ngữ
const masterString = "Unicode Academy Enterprise Training";
const target = "Enterprise";

if (masterString.includes(target)) {
    console.log("Tìm thấy chuỗi con!");
}

// Mô hình Brute Force cơ bản để hiểu bản chất
function bruteForceSearch(text, pattern) {
    const n = text.length;
    const m = pattern.length;
    for (let i = 0; i <= n - m; i++) {
        let j = 0;
        while (j < m && text[i + j] === pattern[j]) {
            j++;
        }
        if (j === m) return i; // Trả về chỉ mục bắt đầu
    }
    return -1;
}
Kinh nghiệm thực chiến
Trong phát triển ứng dụng thông thường, hãy ưu tiên sử dụng các hàm có sẵn (built-in methods) vì chúng đã được tối ưu hóa ở tầng mã máy. Chỉ tự cài đặt các thuật toán nâng cao như KMP hoặc Rabin-Karp khi làm việc với các bài toán xử lý chuỗi cực lớn hoặc yêu cầu đặc thù về thuật toán.

Làm thế nào để phát hiện nhanh một chuỗi có phải là chuỗi con (Substring) nằm trong một chuỗi lớn hay không, và độ phức tạp thời gian của các phương pháp tìm kiếm cơ bản là gì?

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi strings liên quan cùng chủ đề