Giải bài trực tuyến

Đây là một bài để các bạn luyện tập về Trie

Cho một danh sách từ L và một từ w . Nhiệm vụ của bạn là phải tìm một từ trong L tạo thành một "vần hoàn hảo" với w . Từ u này là duy nhất xác định bởi các thuộc tinh sau:

• Nó nằm trong L .
• Nó khác w .
• Phần hậu tố chung của chúng dài nhất có thể.
• u là từ có thứ tự từ điển nhỏ nhất thoả mãn các điều trên

Chú ý 

Một tiền tố của một từ là một chuỗi có thể thu được bằng cách lặp lại việc xoá kí tự cuối cùng của từ. Tương tự, một hậu tố của một từ là một chuỗi mà có thể thu được bằng cách lặp lại việc xoá kí tự đầu tiên của từ.

Ví dụ với từ: different.

Từ này vừa là tiền tố, vừa là hậu tố của chính nó. một tiền tố dài nhất khác của nó differen , và một hậu tố dài nhất khác của nó là ifferent . Chuỗi rent cũng là một hậu tố khác nhưng ngắn hơn. Chuỗi eent và iffe đều không phải là tiền tố hay hậu tố của từ different .

Gọi u và v là 2 từ khác nhau. Ta nói rằng u có thứ tự từ điển nhỏ hơn v nếu hoặc u là một tiền tố của v , hoặc nếu i là vị trí đầu tiên mà chúng khác nhau, và kí tự thứ i của u đứng trước kí tự thứ i của v trong bảng chữ cái.

Ví dụ, dog nhỏ hơn dogs , từ này lại nhỏ hơn dragon (Vì o nhỏ hơn r ).

Dữ liệu

Có 2 phần. Phần thứ nhất chứa danh sách từ L , mỗi từ trên 1 dòng. Mỗi từ chỉ chứa các chữ cái thường tiếng Anh và không có 2 nào từ giống nhau.

Phần thứ nhất kết thúc bằng một dòng trống.

Tiếp theo là phần 2, với mỗi câu hỏi cho từ w trên một dòng.

Bạn có thể chắc chắn rằng trong cả 2 phần của dữ liệu vào, độ dài của mỗi từ không quá 30. Và số lượng từ trong mỗi phần không quá 250000.

Kết quả

Với mỗi câu hỏi, viết ra trên một dòng từ mà tạo thành vần hoàn hảo với nó. Kết quả phải viết bằng chữ cái thường.

Ví dụ

Dữ liệu
perfect
rhyme
crime
time

crime
rhyme

Kết quả
time
crime

Trong câu hỏi thứ 2, có 2 từ có cùng độ dài hậu tố với rhyme (là crime và time), từ có thứ tự từ điển nhỏ hơn đã được chọn.

Cảnh báo: File dữ liệu và kết quả rất lớn, cẩn thận với một số ngôn ngữ