CHAIN2 - Chuỗi từ
Giới hạn- Thời gian: 0.4s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Chuỗi từ có độ dài n là một dãy các từ w 1 , w 2 , ..., w n sao cho với mọi 1 ≤ i < n, từ w i là tiền tố của từ w i+1 .
Nhắc lại từ u có độ dài k là tiền tố của từ v có độ dài l nếu l > k và các ký tự đầu tiên của v trùng với từ u.
Cho tập hợp các từ S={s 1 , s 2 , ..., s m }. Tìm chuỗi từ dài nhất có thể xây dựng được bằng cách dùng các từ trong tập hợp S (có thể không sử dụng hết các từ).
Dữ liệu
Dòng đầu tiên chứa số nguyên m (1 ≤ m ≤ 250000). Mỗi dòng trong số m dòng sau chứa một từ trong tập S.
Biết rằng mỗi từ có độ dài không quá 250000 ký tự và tổng độ dài của các từ không vượt quá 250000 ký tự.
Kết quả
In ra một số duy nhất là độ dài của chuỗi từ dài nhất xây dựng được từ các từ trong tập đã cho.
Ví dụ
Dữ liệu 3 a ab abc Kết quả 3 Dữ liệu 5 a ab bc bcd add Kết quả 2
Nguồn: Цикл Интернет-олимпиад для школьников, сезон 2007-2008
- Người up: paulmcvn