Văn phạm thay thế hậu tố
Đề bài
Mô tả
Là lập trình viên, hẳn bạn đã nghe về biểu thức chính quy và văn phạm phi ngữ cảnh. Đó là những cách phong phú để sinh ra các tập xâu trên một bảng chữ cái nhỏ (còn gọi là một ngôn ngữ hình thức). Còn có những cách khác, ít phổ biến hơn, để sinh ra ngôn ngữ, chẳng hạn văn phạm kề cây, văn phạm cảm ngữ cảnh và văn phạm không hạn chế. Bài toán này dùng một cách mới để sinh ra ngôn ngữ: văn phạm thay thế hậu tố.
Một văn phạm thay thế hậu tố gồm một xâu bắt đầu và một tập các luật thay thế hậu tố. Mỗi luật có dạng , trong đó và là hai xâu có cùng độ dài, gồm các ký tự chữ cái và chữ số. Luật này có nghĩa là nếu hậu tố (tức là các ký tự ở cuối bên phải) của xâu hiện tại là thì bạn có thể thay hậu tố đó bằng . Các luật có thể được áp dụng bao nhiêu lần tùy ý.
Ví dụ, giả sử có luật A B, AB BA, AA CC và CC BB. Khi đó bạn có thể biến xâu AA thành BB bằng ba lần áp dụng luật: AA AB (dùng luật A B), rồi AB BA (dùng luật AB BA), và cuối cùng BA BB (lại dùng luật A B). Nhưng bạn cũng có thể biến đổi nhanh hơn, chỉ với lần áp dụng luật: AA CC rồi CC BB.
Hãy viết chương trình nhận một văn phạm thay thế hậu tố và một xâu , xác định xem xâu bắt đầu của văn phạm có thể biến đổi thành xâu hay không. Nếu có thể, chương trình còn phải tìm số lần áp dụng luật ít nhất để thực hiện việc biến đổi đó.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai xâu và có cùng độ dài, gồm các ký tự chữ cái và chữ số (mỗi xâu dài từ đến ký tự, cách nhau bởi khoảng trắng), và một số nguyên là số luật. Mỗi dòng trong dòng tiếp theo chứa hai xâu và có cùng độ dài, gồm các ký tự chữ cái và chữ số (mỗi xâu dài từ đến ký tự, cách nhau bởi khoảng trắng), cho biết là một luật của văn phạm. Mọi xâu đều phân biệt chữ hoa và chữ thường.
Sau bộ test cuối cùng là một dòng chứa một dấu chấm (.).
Dữ liệu ra
Với mỗi bộ test, in số thứ tự của bộ test (bắt đầu từ ) và số lần áp dụng luật ít nhất cần để biến thành . Nếu không thể biến đổi được, in No solution. Làm theo đúng định dạng trong ví dụ.
Ràng buộc
- , .
- với mọi luật (luật có thể dài hơn ).
- Các xâu chỉ gồm chữ cái
A-Z,a-zvà chữ số0-9. - Mỗi file có không quá bộ test và tổng các giá trị trong một file không quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| AA BB 4 A B AB BA AA CC CC BB A B 3 A C B C c B . |
Case 1: 2 Case 2: No solution |
Bộ test 1 là ví dụ trong đề: AA CC BB. Bộ test 2: từ A chỉ đi được tới C, còn luật c B dùng chữ c thường, không áp dụng được cho C. |
| 000 111 3 0 1 01 10 011 100 ab ab 0 xY xy 2 y Y xxY xxy . |
Case 1: 7 Case 2: 0 Case 3: No solution |
Bộ test 1: các luật đếm nhị phân, 000 001 010 011 100 101 110 111. Bộ test 2: , không cần áp dụng luật nào. Bộ test 3: luật y Y không áp dụng được cho xY, còn luật xxY xxy dài hơn xâu. |
Bình luận