Rima
레이팅 미적용의견: 0
1 \(s / 256\) \(MB / 140\) points
Little Adrian is a fan of rhyme. He believes that two words rhyme if and only if their longest
common suffix is as long as the longer of the two words, or shorter than the longer word by
1. In other words, \(A\)
and \(B\)
rhyme if and only if it holds
.
\(CS\)(\(A\), \(B\))
\(ax\)(|\(A\)|, |\(B\)|)
1
\(L\)
≥\(m\)
−
One day, while reading a collection of short stories, he decided to compose the longest
possible sequence of words such that each two consecutive words rhyme. Each word from
the sequence can appear only once.
Adrian has grown tired of this task, so he decided to go back to reading, and is asking you to
solve this task instead of him.
In test cases worth 30% of points, it will hold \(N \le 18\).
The first line of input contains the integer \(N\)
(1 ≤ \(N\)
≤ 500 000).
Each of the following \(N\)
lines contains one word consisting of lowercase letters of the English
alphabet. All words are mutually distinct, and their total length is at most 3 000 000.
You must output the length of the longest sequence.
4
honi
toni
oni
ovi
5
ask
psk
krafna
sk
k
5
pas
kompas
stas
s
nemarimeoutput
output
3
4
1Clarification of the second test case:
The only possible sequence is ask-psk-sk-k
.
Clarification of the third test case:
No two words rhyme.
평가 및 의견
Rima
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Rima