Nén dãy xâu bằng phần gối đầu
Points
80
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề 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$
Community Discussion