Olympiad in Informatics

GIẢI MÃ CHỮ VIẾT CỦA NGƯỜI MAIA

Công việc giải mã chữ viết của người MAIA là khó khăn hơn người ta tưởng nhiều. Trải qua hơn 200 năm mà người ta vẫn hiểu rất ít về các chữ viết này. Chỉ trong 3 thập niên gần đây do công nghệ phát triển việc giải mã này mới có nhiều tiến bộ.

Chữ viết Maia dựa trên các ký hiệu nhỏ gọi là nét vẽ, mỗi nét vẽ tương ứng với một âm giọng nói. Mỗi từ trong chữ viết Maia sẽ bao gồm một tập hợp các nét vẽ như vậy kết hợp lại với nhiều kiểu dáng khác nhau. Mỗi nét vẽ có thể hiểu là một ký tự ta hiểu ngày nay.

Một trong những vấn đề lớn khi giải mã chữ Maia là thứ tự đọc các nét vẽ. Do người Maia trình bày các nét vẽ này không theo thứ tự phát âm, mà theo cách thể hiện của chúng. Do vậy nhiều khi đã biết hết các nét vẽ của một từ rồi nhưng vẫn không thể tìm ra được chính xác cách ghi và đọc của từ này.

Các nhà khảo cổ đang đi tìm kiếm một từ đặc biệt W. Họ đã biết rõ tất cả các nét vẽ của từ này nhưng vẫn chưa biết các cách viết ra của từ này. Vì họ biết có các thí sinh IOI'06 sẽ đến nên muốn sự trợ giúp của các sinh viên này. Họ sẽ đưa ra toàn bộ g nét vẽ của từ W và dãy S tất cả các nét vẽ có trong hang đá cổ. Bạn hãy giúp các nhà khảo cổ tính xem có bao nhiêu khả năng xuất hiện từ W trong hang đá.

Yêu cầu

Hãy viết chương trình, cho trước các ký tự của từ W và dãy S các nét vẽ trong hang đá, tính tổng số khả năng xuất hiện của từ W trong dãy S, nghĩa là số lần xuất hiện một hoán vị các ký tự của dãy g ký tự trong S.

Các ràng buộc

• 1 ≤ g ≤ 3 000, số nét vẽ trong W
• g ≤ |S| ≤ 3 000 000, |S| là số các nét vẽ của dãy S

Dữ liệu

Dòng 1: chứa 2 số g và |S| cách nhau bởi dấu cách.

Dòng 2: chứa g ký tự liền nhau là các nét vẽ của từ W. Các ký tư hợp lệ là 'a'-'z' và 'A'-'Z'. Các chữ in hoa và in thường là khác nhau.

Dòng 3: Chứa |S| ký tự là dãy các nét vẽ tìm thấy trong hang. Các ký tư hợp lệ là 'a'-'z' và 'A'-'Z'. Các chữ in hoa và in thường là khác nhau.

Dữ liệu mẫu
4  11
cAda
AbrAcadAbRa

Kết quả

Dòng 1: Chứa đúng 1 số là khả năng xuất hiện của từ W trong dãy S.

Kết quả mẫu
2

Chấm điểm

Có một số Test với tổng điểm 50 với giá trị g ≤ 10.