Nén dãy xâu bằng phần gối đầu

General
Points
80
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho $k$ xâu ký tự $S_1, S_2, \dots, S_k$. Ban đầu xâu kết quả $R = S_1$. Lần lượt với $i = 2, \dots, k$, ta ghép $S_i$ vào cuối $R$ sao cho phần hậu tố của $R$ trùng với phần tiền tố của $S_i$ nhiều nhất có thể (tức tìm $L$ lớn nhất sao cho $L \le \min(|R|, |S_i|)$ và $L$ ký tự cuối của $R$ bằng $L$ ký tự đầu của $S_i$, rồi chỉ nối phần $S_i[L..|S_i|-1]$ vào $R$). Hãy in ra độ dài cuối cùng của xâu $R$.

Dữ liệu vào

Dòng đầu chứa số nguyên $k$. $k$ dòng tiếp theo, mỗi dòng chứa một xâu $S_i$.

Dữ liệu ra

In ra độ dài cuối cùng của xâu $R$.

Ví dụ
Input Output
3
iwant
to
order
10
Giới hạn
  • $1 \le k \le 10^4$
  • Tổng độ dài các xâu $\le 10^5$
Draft saved