cpp-250Bước 1Cơ bản
Đếm số từ trong câu
Đếm từ là bước đầu của phân tích văn bản và kiểm tra giới hạn nội dung. Văn bản thật thường có nhiều khoảng trắng liên tiếp và khoảng trắng ở hai đầu, nên cách tách từ phải chịu đư…
CHUYÊN ĐỀ C++ THỰC CHIẾN
Bài tập Xâu ký tự (String) & Xử lý văn bản trong C++
Luyện tập các phương thức của lớp std::string và các thuật toán so khớp mẫu kinh điển giúp giải quyết các bài toán chuỗi lớn với độ phức tạp tuyến tính O(N).
27
bài tập có chấm code
Bài tập theo chuyên đề, có đề bài, ví dụ và starter code riêng.
14
cơ bản
Củng cố nền tảng và làm quen với kỹ thuật cốt lõi.
3
trung bình
Kết hợp nhiều bước suy luận để vận dụng kiến thức.
10
nâng cao
Thử thách tối ưu, cấu trúc dữ liệu và thuật toán chuyên sâu.
Lộ trình thực hành đề xuất
Bước 1
String STL cơ bản
Đọc xâu với getline, nối xâu, so sánh và các phương thức substr, find, size.
Bước 2
Bảng đếm tần suất
Dùng mảng int count[256] để đếm ký tự trong thời gian O(N) và bộ nhớ O(1).
Bước 3
Xâu đối xứng & Biến đổi
Kiểm tra palindrome, nén xâu RLE và đảo ngược các từ trong câu.
Bước 4
Thuật toán Rolling Hash
So khớp chuỗi con và tìm kiếm xâu con lặp lại dài nhất trong thời gian kỳ vọng O(N).
Lỗi thường gặp & Cách phòng tránh
•
Dùng cin >> s thay vì getline(cin, s) khi chuỗi đầu vào có chứa khoảng trắng.
•
Trôi lệnh khi dùng getline ngay sau khi đọc số bằng cin (quên cin.ignore()).
Danh sách bài tập thực hành (27 bài)
Trong mỗi mức độ, bài tập được xếp từ dễ nhất đến khó nhất — hãy đi theo số bước.
Cơ bản 14 bài
Khởi động
Nhập xuất, biến, rẽ nhánh và các bước suy luận đơn giản.
cpp-251Bước 2Cơ bản
Từ dài nhất trong câu
Tìm cực trị kèm quy tắc hoà giải rất phổ biến: khi nhiều từ cùng độ dài, phải chọn từ xuất hiện trước. Đây là ví dụ điển hình cho việc chọn đúng toán tử so sánh.
cpp-270Bước 3Cơ bản
Kiểm tra hai chuỗi đảo chữ
Hai chuỗi là đảo chữ khi chúng có cùng đa tập ký tự — giống nhau về ký tự và số lần xuất hiện, chỉ khác thứ tự. Mảng đếm 26 phần tử cho lời giải O(L).
cpp-269Bước 4Cơ bản
Mã hoá Caesar
Mã Caesar dịch mỗi chữ cái đi k vị trí trong bảng chữ cái và quay vòng khi vượt z. Đây là bài nhập môn số học modulo trên ký tự và là bước đệm hiểu mã thay thế, ROT13.
cpp-252Bước 5Cơ bản
Đếm độ dài từ
In kết quả xử lý chuỗi.
cpp-253Bước 6Cơ bản
Lấy ký tự đầu
In kết quả xử lý chuỗi.
cpp-254Bước 7Cơ bản
Lấy ký tự cuối
In kết quả xử lý chuỗi.
Làm quen
Vòng lặp, mảng một chiều, chuỗi và hàm ở mức cơ bản.
cpp-255Bước 8Cơ bản
Đếm ký tự a
In kết quả xử lý chuỗi.
cpp-256Bước 9Cơ bản
Đảo ngược từ
In kết quả xử lý chuỗi.
cpp-257Bước 10Cơ bản
Đếm nguyên âm
In kết quả xử lý chuỗi.
cpp-258Bước 11Cơ bản
Kiểm tra đối xứng
In kết quả xử lý chuỗi.
cpp-259Bước 12Cơ bản
Nối từ hai lần
In kết quả công thức trong tên bài.
cpp-260Bước 13Cơ bản
Lấy ký tự giữa
In kết quả xử lý chuỗi.
cpp-261Bước 14Cơ bản
Đếm khoảng trắng
In kết quả xử lý chuỗi.
Trung bình 3 bài
cpp-005Bước 1Trung bình
Chuẩn hóa họ tên và tạo email học viên
Cổng thông tin tuyển sinh trực tuyến của AI Empire Academy tiếp nhận hồ sơ học viên với họ tên viết dưới dạng xâu ký tự thô (gồm các chữ cái tiếng Anh/tiếng Việt không dấu a-z, A-Z…
cpp-126Bước 2Trung bình
Đảo Ngược Từng Từ Trong Chuỗi Ký Tự
Cho một chuỗi ký tự S gồm các từ được phân cách bởi một hoặc nhiều dấu cách.
cpp-127Bước 3Trung bình
Kiểm Tra Chuỗi Đảo Chữ (Valid Anagram)
Cho hai chuỗi ký tự S và T chỉ chứa các chữ cái tiếng Anh in thường ('a' đến 'z').
Nâng cao 10 bài
Thử thách
Thuật toán chuyên sâu: quy hoạch động, đồ thị, cây.
cpp-188Bước 1Nâng cao
Cây đối xứng (Palindromic Tree / EerTree): Đếm xâu con đối xứng phân biệt
Cho một xâu S gồm N chữ cái tiếng Anh in thường.
cpp-050Bước 2Nâng cao
Thuật toán Manacher tìm xâu con đối xứng (Palindrome) dài nhất trong O(N)
Cho một xâu ký tự S gồm N chữ cái thường tiếng Anh ('a' đến 'z'). Hãy tìm độ dài của xâu con liên tiếp đối xứng (Palindrome) dài nhất trong S.
cpp-051Bước 3Nâng cao
Thuật toán Z-Algorithm xây dựng mảng Z-Function trong O(N)
Cho một xâu ký tự S gồm N chữ cái thường tiếng Anh ('a' đến 'z'). Hãy tính mảng Z của xâu S, với quy ước Z[0] = 0.
cpp-190Bước 4Nâng cao
Mảng hậu tố (Suffix Array): Tìm kiếm và đếm số lần xuất hiện của mẫu
Cho một văn bản T gồm N chữ cái tiếng Anh in thường.
cpp-029Bước 5Nâng cao
Thuật toán Knuth-Morris-Pratt (KMP) so khớp mẫu xâu
Trong công cụ kiểm duyệt và phát hiện đạo văn tại AI Empire Academy, hệ thống cần tìm kiếm sự xuất hiện của một đoạn mã mẫu P (Pattern) bên trong văn bản mã nguồn lớn T (Text). Với…
Chuyên sâu
Cấu trúc dữ liệu nâng cao và nhiều bước chứng minh.
cpp-028Bước 6Nâng cao
Cây tiền tố Trie: Từ điển tra cứu và đếm tiền tố
Bộ máy gợi ý thông minh (Auto-complete Search) của AI Empire Academy cần tối ưu hóa tốc độ phản hồi khi học viên tìm kiếm thuật toán. Bạn được giao xây dựng cấu trúc Cây tiền tố (T…
cpp-053Bước 7Nâng cao
Mảng hậu tố Suffix Array và mảng LCP bằng thuật toán Kasai trong O(N log N)
Cho một xâu ký tự S gồm N chữ cái thường tiếng Anh ('a' đến 'z'). Hãy xây dựng:
cpp-049Bước 8Nâng cao
Tự động Aho-Corasick tìm kiếm đồng thời nhiều xâu mẫu
Hệ thống kiểm duyệt nội dung của AI Empire Academy cần tìm kiếm sự xuất hiện của K từ khóa mẫu P1, P2, …, PK bên trong một đoạn văn bản T.
cpp-052Bước 9Nâng cao
Máy tự động hậu tố Suffix Automaton (SAM) đếm số xâu con phân biệt
Cho một xâu ký tự S gồm N chữ cái thường tiếng Anh ('a' đến 'z'). Hãy đếm số lượng xâu con liên tiếp phân biệt (Distinct Substrings) xuất hiện trong S.
cpp-189Bước 10Nâng cao
Suffix Automaton (SAM): Xâu con chung dài nhất của K xâu
Cho K xâu ký tự S1, S2, …, SK chỉ gồm các chữ cái tiếng Anh in thường.