Việc giải mã chữ viết Maya đã tỏ ra khó khăn hơn những gì các nghiên cứu ban đầu dự đoán. Sau gần hai trăm năm, người ta vẫn chỉ hiểu được rất ít về loại chữ viết này. Chỉ trong ba thập kỷ gần đây mới có những tiến bộ thực sự.

Chữ viết Maya dựa trên các hình vẽ nhỏ gọi là ký tự tượng hình, dùng để biểu diễn âm thanh. Các từ trong tiếng Maya thường được viết bằng cách ghép những ký tự tượng hình ở các vị trí khác nhau.

Một trong những khó khăn khi giải mã chữ viết Maya là xác định thứ tự đọc. Khi sắp xếp các ký tự tượng hình để tạo thành một từ, đôi khi người viết lựa chọn vị trí dựa vào quan điểm thẩm mỹ của riêng mình nhiều hơn là theo một quy tắc cụ thể. Vì vậy, dù đã biết âm thanh ứng với nhiều ký tự, các nhà khảo cổ đôi khi vẫn không chắc phải phát âm một từ được viết ra như thế nào.

Các nhà khảo cổ đang tìm một từ đặc biệt \(W\). Họ biết các ký tự tượng hình của từ này nhưng không biết tất cả những cách có thể sắp xếp chúng. Biết rằng bạn sẽ tham dự IOI 2006, họ đã nhờ bạn giúp đỡ. Họ sẽ cung cấp \(g\) ký tự tượng hình của \(W\) và một dãy \(S\) gồm tất cả các ký tự tượng hình trong những bản khắc đang được nghiên cứu, theo đúng thứ tự xuất hiện. Hãy giúp họ đếm số lần từ \(W\) có thể xuất hiện.

Cho các ký tự tượng hình của \(W\) và dãy \(S\), hãy viết chương trình đếm số đoạn gồm đúng \(g\) ký tự liên tiếp trong \(S\) là một hoán vị của các ký tự trong \(W\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên cách nhau bởi một dấu cách, lần lượt là \(g\) và \(|S|\).
• Dòng thứ hai chứa \(g\) ký tự liên tiếp biểu diễn các ký tự tượng hình trong \(W\).
• Dòng thứ ba chứa \(|S|\) ký tự liên tiếp biểu diễn các ký tự tượng hình trong những bản khắc, tạo thành dãy \(S\).

Các ký tự hợp lệ trong cả \(W\) và \(S\) là a đến z và A đến Z. Chữ hoa và chữ thường được coi là khác nhau.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số lần \(W\) có thể xuất hiện trong \(S\).

Ràng buộc

• \(1 \le g \le 3\,000\), trong đó \(g\) là số ký tự tượng hình trong \(W\).
• \(g \le |S| \le 3\,000\,000\), trong đó \(|S|\) là số ký tự tượng hình trong \(S\).

Phân nhóm

Trong một tập các bộ dữ liệu kiểm tra có tổng cộng \(50\) điểm, mỗi lần chạy đều thỏa mãn \(g \le 10\).

Ví dụ

4 11
cAda
AbrAcadAbRa

2

Lưu ý cho người dùng Pascal

Theo mặc định trong FreePascal, một biến kiểu string có giới hạn độ dài là \(255\) ký tự. Để sử dụng xâu dài hơn, hãy thêm chỉ thị {$H+} ngay bên dưới dòng program ...; trong mã nguồn.

Nguồn

IOI 2006, ngày thi thứ nhất: Deciphering the Mayan Writing, bản tiếng Anh 1.3. Tác giả đề bài: Cesar Cepeda (Mexico).