LPREFIX - Xâu tiền tố dài nhất
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: Biển

Xâu A được gọi là tiền tố của xâu B nếu length(A) <= length(B) và sau khi ta xóa đi một số kí tự cuối cùng của B thì thu được xâu A.

Yêu cầu: Cho N xâu, bạn hãy tìm một xâu dài nhất sao cho nó là tiền tố của ít nhất 2 trong số N xâu đã cho. Nếu có nhiều xâu thỏa mãn có cùng độ dài, hãy đưa ra đáp án xuất hiện đầu tiên theo thứ tự từ điển.

Dữ liệu: Vào từ file văn bản LPREFIX.INP:

  • Dòng thứ nhất ghi số nguyên dương N (2 ≤ N ≤ 5000).
  • Dòng thứ i trong N dòng tiếp theo ghi xâu Wi (2 ≤ length(Wi) ≤ 100).

Kết quả: Ghi ra file văn bản LPREFIX.OUT một dòng duy nhất ghi xâu tiền tố dài nhất thỏa mãn yêu cầu đề bài.

Ví dụ

Input:

7

CHEDDAR

CHESSO

CHAOURCE

PARMESAN

CHAUMES

ROQUEFORT

POSSIA

Output:

CHA

Giải thích: Các xâu là tiền tố của ít nhất 2 xâu là C, CH, CHA, CHE, P. Xâu dài nhất là xâu CHA và CHE nhưng xâu CHA xuất hiện trước CHE trong thứ tự từ điển.


Bài 2 HSG 9 TP Đà Nẵng 2014 - 2015

Back to Top