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:
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.
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