COCI 2016/2017 - Contest 4 - Rima

View as PDF

Submit solution

Points: 1.40 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 4
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Adrian là một fan cuồng vần điệu. Anh ấy tin rằng hai từ có vần điệu khi và chỉ khi hậu tố chung ~(LCS)~ của chúng có độ dài bằng độ dài từ dài hơn trong hai từ hoặc ngắn hơn độ dài từ dài trong hai từ một chữ cái. Nói cách khác, ~A~ và ~B~ được cho là có vần khi và chỉ khi ~LCS (A, B) ≥ max (|A|, |B|) - 1~.

Một ngày nọ, trong lúc đang đọc một tập truyện ngắn, anh quyết định tạo ra chuỗi dài nhất có thể có sao cho hai từ liên tiếp nhau đều có vần. Mỗi từ trong chuỗi chỉ được xuất hiện một lần.

Adrian đã cảm thấy mệt mỏi với nhiệm vụ này, vì vậy anh ấy quyết định tiếp tục đọc truyện, bạn hãy giải quyết nhiệm vụ này giúp anh ta.

Input

Dòng đầu tiên chứa số nguyên ~N~ ~(1 \leq N \leq 5 \times 10^5)~.

~N~ dòng tiếp theo mỗi dòng chứa một từ gồm các chữ cái viết thường. Các từ phân biệt đôi một và tổng độ dài của chúng tối đa ~3 \times 10^6~.

Output

Ghi ra độ dài của chuỗi dài nhất.

Sample Input 1

4
honi
toni
oni 
ovi

Sample Output 1

3

Sample Input 2

5
ask
psk
krafna
sk
k

Sample Output 2

4

Giải thích ví dụ 2: ask-psk-sk-k

Sample Input 3

5
pas
kompas
stas
s
nemarime

Sample Output 3

1

Giải thích ví dụ 3: Không có hai từ nào có vần điệu với nhau.

Subtask

  • ~30\%~ số test có ~N \le 18~
  • ~70\%~ số test còn lại không có điều kiện gì thêm

Comments

Please read the guidelines before commenting.


There are no comments at the moment.