Nội dung Bài tập
- Mã:
- OLP17.SC1.PREFIX
- Tên:
- Hàm tiền tố
- Dạng thi:
- oi
- Thang điểm:
- 100 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- admin
Khi học môn “Mã hóa và nén dữ liệu”, Tuấn rất hứng thú với những phương pháp mã hóa đòi hỏi ít bộ nhớ hơn nhiều so với mã hóa ACSII thông dụng. Vừa rồi, khi khảo sát những xâu chứa nhiều ký tự liên tiếp giống nhau, Tuấn phát hiện ra rằng có thể thiết lập tương ứng một-một giữa một xâu S như vậy với một dãy số nguyên dương và một dãy các ký tự. Cụ thể là: xâu S bắt đầu bởi a1 ký tự c1, tiếp đến là a2 ký tự c2, …, và cuối cùng là an ký tự cn:
được đặt tương ứng với dãy số nguyên dương A = (a1, a2, …, an) và xâu ký tự C = c1c2…cn.
Việc mã hóa và giải mã theo cách mã hóa như vậy là hết sức đơn giản. Hơn nữa, Tuấn cũng chỉ ra những tình huống ứng dụng mà phương pháp mã hóa này có thể đòi hỏi ít bộ nhớ. Bây giờ một vấn đề nảy sinh trong ứng dụng là cần giải quyết bài toán tìm kiếm xâu mẫu trên xâu mã hóa theo phương pháp này. Tuấn có ý định áp dụng thuật toán KMP (Knuth-Morris-Pratt), mà như đã biết vấn đề đầu tiên cần giải quyết là tính giá trị của hàm tiền tố đối với xâu S được định nghĩa như sau: Với mỗi p = 1, 2, …, l (l là độ dài của xâu S):
trong đó ký hiệu S[u…v] để chỉ xâu con gồm các ký tự liên tiếp từ vị trí u đến vị trí v của xâu S (theo định nghĩa, nếu u>v thì S[u, v] là xâu rỗng).
Hãy giúp Tuấn giải quyết vấn đề đặt ra, cụ thể bạn được yêu cầu giải quyết vấn đề sau đây:
Yêu cầu: Cho dãy số A và dãy ký tự C là mã hóa của xâu S và m truy vấn p1, p2, …, pm, hãy đưa ra giá trị của hàm tiền tố 
với mỗi i = 1, 2, …, m.
với mỗi i = 1, 2, …, m.Dữ liệu input:
- Dòng đầu tiên chứa số nguyên dương n, m (n, m ≤ 105);
- Dòng thứ hai chứa n số nguyên dương a1, a2, …, an (ai ≤ 109, 1 ≤ i ≤ n) mô tả dãy A;
- Dòng thứ ba là xâu C gồm n ký tự c1c2…cn, các ký tự được lấy từ bảng chữ cái tiếng Anh chữ in thường được viết liên tiếp nhau, và ci khác ci+1, i = 1, 2, …, n-1;
- Dòng cuối cùng chứa m số nguyên dương p1, p2, …, pm (1 ≤ pi ≤ l, 1 ≤ i ≤ m) là m truy vấn cần được trả lời.
Các số trên cùng dòng được ghi cách nhau bởi dấu cách.
Kết quả: Xuất trên một dòng các giá trị 
là các câu trả lời cho các truy vấn. Các số được ghi cách nhau bởi một dấu cách.
là các câu trả lời cho các truy vấn. Các số được ghi cách nhau bởi một dấu cách.Ví dụ:
Input Output
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
THPT_NK_DEQUY
#include <iostream>using namespace std;int main(){ cout << "Co ga...