[Buổi 1][Tư duy giải bài & Độ phức tạp][HW] Bài 1: Nhịp tín hiệu dài nhất
Nhịp tín hiệu dài nhất
Bối cảnh và bài toán
Trong một bước kiểm tra chất lượng dữ liệu giải trình tự DNA, hệ thống nhận một chuỗi chỉ gồm bốn ký hiệu A, C, G, T. Một đoạn liên tiếp chứa cùng một ký hiệu quá lâu có thể là đặc trưng đáng chú ý của mẫu hoặc dấu hiệu cần kiểm tra thêm.
Gọi một nhịp lặp là một đoạn liên tiếp mà mọi ký tự đều giống nhau.
Yêu cầu
Tìm độ dài lớn nhất của một nhịp lặp trong chuỗi.
Input
Một dòng chứa chuỗi s.
Output
Một số nguyên — độ dài nhịp lặp dài nhất.
Ràng buộc
1 <= |s| <= 10^6s[i]thuộcA, C, G, T
Chấm điểm
| Subtask | Điểm | Điều kiện | Official tests |
|---|---|---|---|
| S1 | 30% | |s| ≤ 100 | 01–03 |
| S2 | 70% | Không có ràng buộc bổ sung | 04–10 |
Ví dụ 1
Input
ATTCGGGA
Output
3
Giải thích. Các đoạn lặp đáng chú ý gồm TT dài 2 và GGG dài 3; lớn nhất là 3.
Ví dụ 2
Input
AAAAA
Output
5
Giải thích. Toàn bộ chuỗi là một nhịp lặp của ký hiệu A, nên đáp án bằng độ dài chuỗi.
Thông tin bài tập
| Thuộc tính | Giá trị |
|---|---|
| Mã bài | DSA-M01-B01-HW01 |
| Buổi | B01 |
| Loại bài | HOMEWORK |
| Mức độ khó | Dễ (Easy) |
| Thời gian làm bài khuyến nghị | 15 phút |
| Time limit | 1 giây |
| Memory limit | 256 MB |
| Tổng điểm | 100 |
| Chuẩn ngôn ngữ tham chiếu | C++17 |
Nguồn: Phỏng theo CSES Problem Set — Repetitions (Task 1069).
Tham khảo: https://cses.fi/problemset/task/1069/
Ghi chú biên tập: Biên tập lại ngữ cảnh/constraints và chuẩn hóa theo lộ trình FULLHOUSE DEV; giữ bản chất yêu cầu của bài nguồn.
Comments