Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NPR - Vần hoàn hảo

Đâ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 eentiffe đều không phải là tiền tố hay hậu tố của từ different.

Gọi uv 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ữ

Được gửi lên bởi:Race with time
Ngày:2008-09-07
Thời gian chạy:3.168s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:IPSC

hide comments
2014-09-25 04:15:30 Anh Duc Le
test bựa >.<
2013-12-15 06:04:24 code quá nhanh ...
test yếu, thiếu test phần hậu tố là rỗng. Có nghĩa k có xâu nào cùng phần hậu tố với w
2013-10-24 04:51:59 Phạm Bá Thái
Phải dùng seekeof các bác à
2011-06-16 12:54:45 T-7
http://www.spoj.pl/problems/PRHYME/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.