408365: GYM103107 E Elastic Search

You are given $$$n$$$ strings $$$s_1, s_2, \cdots, s_n$$$. We call $$$t$$$ a substring of $$$s$$$ if we can get $$$t$$$ by deleting several consecutive characters (probably zero) from the beginning and/or the end of the string $$$s$$$.

We define a multinest of strings as a sequence $$$p_1, p_2, \cdots, p_m ~ (m \leq n)$$$, where $$$p_i$$$ are pair-wise distinct and $$$s_{p_i}$$$ is a substring of $$$s_{p_{i-1}}$$$ for any $$$2 \leq i \leq m$$$. The length of the multinest is the number of elements in the sequence.

Now you need to calculate the maximum possible length of the multinest among the $$$n$$$ strings.

The first line contains an integer $$$n ~ (1 \leq n \leq 500000)$$$, indicating the number of strings.

Then $$$n$$$ lines follows. Each line contains a string $$$s_i$$$ which consists of only lowercase letters.

It is guaranteed that $$$\sum_{i = 1}^n |s_i| \leq 500000$$$.

Only one integer $$$L$$$ which represents the maximum length of the multinest.

6
bcba
cba
cbcb
cba
cb
bcb

4

The longest multinest in the sample is $$$(bcba, cba, cba, cb)$$$ of which the the index sequence is $$$(1, 2, 4, 5)$$$ which has length $$$4$$$.