Problem J
Rimstyrka
Languages
en
sv
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
-
$0$, om ett av orden är ett suffix av det andra.
-
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.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 spaghetti already confetti serengeti |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
8 its not impossible cuz i know its possible |
0 |
