Problem H
Rhyme Power
Languages
en
sv
Rhymes are complicated. The extent to which one word rhymes with another depends on how similar they sound; but if they are too similar then they aren’t considered a rhyme at all. Karim has a huge list of $N$ words and wants to determine the maximally rhyming pair of words. To that end he has introduced the concept of rhyme power:
Given two words $S$ and $T$, their rhyme power $r(S,T)$ is defined as
-
$0$, if one word is a suffix of the other,
-
the length of their longest common suffix, otherwise.
For instance, the rhyme power of “fire” and “desire” is $3$, because their longest common suffix “ire” has length $3$. In contrast, the rhyme power of “impossible” and “possible” is $0$, because “possible” is a suffix of “impossible”.
Given Karim’s list of $N$ words, your task is to find the maximum value of $r(S, T)$ over all pairs of words.
Input
The first line contains an integer $N$ with $2 \leq N \leq 10^5$, the number of words.
The following $N$ lines each contain a string $S_ i$, where $1 \leq |S_ i| \leq 10^6$. The sum of all string lengths $|S_ i|$ is at most $10^6$.
Output
An integer, the maximal rhyme power.
| 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 |
