Chuỗi từ

Xem dạng PDF
Gửi bài giải
Điểm: 0,27 (OI)
Giới hạn thời gian: 0.6s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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 \leq 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 =\left(s_{1}, s_{2}, \dots, s_{m}\right)~. 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ừ).

Input

  • Dòng đầu tiên chứa số nguyên ~m~ ~(1 \leq m\leq 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ự.

Output

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

Sample Input 1

3
a
ab
abc

Sample Output 1

3

Sample Input 2

5
a
ab
bc
bcd
add

Sample Output 2

2

Note

Nguồn: Цикл Интернет-олимпиад для школьников, сезон 2007-2008

Bình luận

Hãy đọc nội quy trước khi bình luận.