Ngôn ngữ ngoài hành tinh

Bài toán

Sau nhiều năm nghiên cứu, các nhà khoa học tại Google Labs đã phát hiện ra một ngôn ngữ ngoài hành tinh được truyền từ một hành tinh xa xôi. Ngôn ngữ ngoài hành tinh này rất độc đáo ở chỗ mọi từ đều có độ dài chính xác là \(L\) chữ cái thường. Ngoài ra, có đúng \(D\) từ trong ngôn ngữ này.

Sau khi xây dựng được từ điển gồm tất cả các từ trong ngôn ngữ ngoài hành tinh, bước đột phá tiếp theo là phát hiện ra rằng người ngoài hành tinh đã gửi thông điệp đến Trái Đất trong suốt thập kỷ qua. Thật không may, những tín hiệu này bị yếu đi do khoảng cách giữa hai hành tinh và một số từ có thể bị hiểu sai. Để giúp họ giải mã những thông điệp này, các nhà khoa học đã yêu cầu bạn thiết kế một thuật toán xác định số lượng cách giải thích có thể cho một mẫu (pattern) cho trước.

Một mẫu bao gồm đúng \(L\) mã thông báo (token). Mỗi mã thông báo là một chữ cái thường duy nhất (các nhà khoa học rất chắc chắn đó là chữ cái đó) hoặc một nhóm các chữ cái thường duy nhất được bao quanh bởi dấu ngoặc đơn ( và ). Ví dụ: (ab)d(dc) có nghĩa là chữ cái đầu tiên là a hoặc b, chữ cái thứ hai chắc chắn là d và chữ cái cuối cùng là d hoặc c. Do đó, mẫu (ab)d(dc) có thể đại diện cho bất kỳ một trong 4 khả năng sau: add, adc, bdd, bdc.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa 3 số nguyên \(L\), \(D\) và \(N\) cách nhau bởi dấu cách. \(D\) dòng tiếp theo, mỗi dòng chứa một từ có độ dài \(L\). Đây là những từ được biết là tồn tại trong ngôn ngữ ngoài hành tinh. \(N\) trường hợp thử nghiệm sau đó, mỗi trường hợp trên một dòng riêng biệt và mỗi trường hợp bao gồm một mẫu như mô tả ở trên. Bạn có thể giả định rằng tất cả các từ đã biết được cung cấp là duy nhất.

Dữ liệu ra

Với mỗi trường hợp thử nghiệm, xuất ra:

Case #X: K

trong đó \(X\) là số thứ tự trường hợp thử nghiệm, bắt đầu từ 1, và \(K\) cho biết có bao nhiêu từ trong ngôn ngữ ngoài hành tinh khớp với mẫu.

Ràng buộc

Phân nhóm

• Tập dữ liệu nhỏ:
• \(1 \le L \le 10\)
• \(1 \le D \le 25\)
• \(1 \le N \le 10\)
• Tập dữ liệu lớn:
• \(1 \le L \le 15\)
• \(1 \le D \le 5000\)
• \(1 \le N \le 500\)

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3 5 4
abc
bca
dac
dbc
cba
(ab)(bc)(ca)
abc
(abc)(abc)(abc)
(zyx)bc

Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0

Nguồn

Google Code Jam 2009, Vòng loại, bài Alien Language.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.