Der Referenzstring
Sie haben eine Liste von
n Zeichenketten, die aus Kleinbuchstaben des lateinischen Alphabets bestehen. Wir nennen eine Zeichenkette s, die aus Kleinbuchstaben des lateinischen Alphabets sowie dem Zeichen # besteht, einen Referenzstring, wenn für jede Zeichenkette in dieser Liste ein Index i in s existiert, bei dem ≠ # gilt und alle Indizes von i bis zum darauffolgenden Vorkommen von # (ohne dieses einzuschließen) genau jene Zeichenkette ergeben. Der Referenzstring muss immer mit dem Zeichen # enden.Schreiben Sie ein Programm, das anhand der gegebenen Liste von Zeichenketten die Länge des kürzesten Referenzstrings ermittelt, der diese Bedingung erfüllt.
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl,
n (1 ≤ n ≤ 100 000), die die Anzahl der Zeichenketten in der Liste angibt.Die folgenden
n Zeilen enthalten die Zeichenketten. Jede Zeichenkette besteht aus Kleinbuchstaben des lateinischen Alphabets und hat eine Länge von höchstens 10.Ausgabe
Das Programm gibt eine einzelne ganze Zahl aus: die Länge des kürzesten Referenzstrings, der die oben genannte Bedingung erfüllt.
Beispiele
Eingabe | Ausgabe |
6
found
profound
ground
round
wound
und | 22 |
3
ab
bc
cd | 9 |
Erklärung
- Beispiel 1: Einer der kürzesten möglichen Referenzstrings ist „
ground#profound#wound#“.
- Beispiel 2: Einer der kürzesten möglichen Referenzstrings ist „
ab#bc#cd#“.
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB