Xâu A được coi là tiền tố của xâu B nếu sau khi ta xóa đi một số kí tự cuối cùng của B, ta thu được xâu A. Cho N xâu, bạn hãy tìm một xâu dài nhất L sao cho nó là tiền tố của ít nhất 2 trong số N xâu. 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
- Dòng thứ nhất ghi số N.
- Dòng thứ i trong N dòng tiếp theo ghi xâu Wi.
Dữ liệu ra :
- Dòng duy nhất ghi ra xâu tìm được.
- Input vào đảm bảo luôn tìm được kết quả.
.png)
Ví dụ
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.
Giới hạn:
- 2 ≤ N ≤ 5000.
- 2 ≤ length(Wi) ≤ 100.
- 1 ≤ length(L) ≤ 99.
Trong 50% số test:
- 2 ≤ N ≤ 1000.
- 2 ≤ length(Wi) ≤ 50.
Đề HSG Tin 9 năm học 2014-2015