Problem C
Rimstyrka

Rim är komplicerade saker. Hur mycket två ord rimmar beror på hur lika varandra de låter, men om de är för lika så rimmar de inte alls. Karim har en enorm lista med $N$ ord, och han vill veta vilka två ord som rimmar mest bland dem. För att kunna göra detta har han introducerat begreppet rimstyrka:

Givet två ord $S$ och $T$ så definieras deras rimstyrka $r(S,T)$ som

1. $0$, om ett av orden är ett suffix av det andra.

2. längden på deras längsta gemensamma suffix annars.

Till exempel har “fire” och “desire” rimstyrka $3$ eftersom deras längsta gemensamma suffix “ire” har längd $3$. Däremot har “impossible” och “possible” rimstyrka $0$ eftersom “possible” är ett suffix av “impossible”.

Du får givet Karims lista med $N$ ord, och din uppgift är att hitta det maximala värdet av $r(S, T)$ över alla par av ord.

Indata

Den första raden innehåller ett heltal $N$ ($2 \leq N \leq 10^5$), antalet ord.

De följande $N$ raderna innehåller en sträng $S_ i$ vardera ($1 \leq |S_ i| \leq 10^6$).

Summan av alla $|S_ i|$ är högst $10^6$.

Utdata

Ett heltal, den maximala rimstyrkan.

4
spaghetti
already
confetti
serengeti

4

8
its
not
impossible
cuz
i
know
its
possible

0