23ος ΠΔΠ Καμπ (seniors)
Τοπωνύμια (toponyms)

Τοπωνύμιο είναι το όνομα μίας πόλης, ενός χωριού, ενός ποταμού, ενός βουνού, κ.λπ. Πολλές φορές συναντά κανείς τοπωνύμια που μοιάζουν πάρα πολύ. Για παράδειγμα «Αγγελόκαστρο Κορινθίας» και «Αγγελόκαστρο Αιτωλοακαρνανίας», ή «Γεροπόταμος» και «Γεροπλάτανος».

Τα τοπωνύμια τα αναπαριστούμε με συμβολοσειρές που αποτελούνται από μικρά και κεφαλαία γράμματα του λατινικού αλφαβήτου \((\texttt{A}, \texttt{B}, \texttt{C}, \ldots, \texttt{Z}, \texttt{a}, \texttt{b}, \texttt{c}, \ldots, \texttt{z})\) και από κενά διαστήματα. Όμως, δεν μπορεί να εμφανίζονται δύο ή περισσότερα διαδοχικά κενά διαστήματα και δεν υπάρχουν κενά διαστήματα στην αρχή ή στο τέλος των τοπωνυμίων. Οι συμβολοσειρές που αποτελούνται από τους m πρώτους χαρακτήρες ενός τοπωνυμίου ονομάζονται «προθέματα» μήκους m, για παράδειγμα η συμβολοσειρά «Γεροπ» είναι ένα πρόθεμα μήκους \(5\) του τοπωνυμίου «Γεροπόταμος».

Ο βαθμός ομοιότητας \(\mathrm{Ls}(T)\) ενός συνόλου τοπωνυμίων \(T\) είναι το μήκος του μακρύτερου κοινού προθέματος όλων των τοπωνυμίων του \(T\). Για παράδειγμα, για το σύνολο \(T = \lbrace «\texttt{Γεροπλάτανος}», «\texttt{Γεροπόταμος}», «\texttt{Γεροβασιλιώτικα}»\rbrace\), ο βαθμός ομοιότητας είναι \(\mathrm{Ls}(T) = 4\) γιατί το μακρύτερο κοινό πρόθεμα είναι «Γερο».

Ο βαθμός πολυπλοκότητας \(\mathrm{Lc}(T)\) ενός συνόλου \(T\) αποτελούμενου από \(k\) τοπωνύμια ορίζεται ως

\[\mathrm{Lc}(T) = k \times \mathrm{Ls}(T)\]

Για παράδειγμα, για το σύνολο \(T = \lbrace «\texttt{Γεροπλάτανος}», «\texttt{Γεροπόταμος}», «\texttt{Γεροβασιλιώτικα}»\rbrace\), ο βαθμός πολυπλοκότητας είναι \(\mathrm{Lc}(T) = 3 \times 4 = 12\).

Γράψτε ένα πρόγραμμα που για κάθε δεδομένο σύνολο τοπωνυμίων \(S\) βρίσκει το υποσύνολο \(Τ \subseteq S\) με το μέγιστο βαθμό πολυπλοκότητας.

Αρχεία Εισόδου (toponyms.in):

Η πρώτη γραμμή της εισόδου θα περιέχει το πλήθος των τοπωνυμίων \(N\). Κάθε μία από τις επόμενες \(N\) γραμμές περιέχει ένα τοπωνύμιο, δηλαδή μία συμβολοσειρά αποτελούμενη από γράμματα και κενά διαστήματα, με τους περιορισμούς που αναφέρθηκαν για τη χρήση των κενών διαστημάτων.

Αρχεία Εξόδου (toponyms.out):

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει ακριβώς έναν ακέραιο αριθμό, το μέγιστο βαθμό πολυπλοκότητας που μπορεί να έχει κάποιο υποσύνολο των τοπωνυμίων.

Παράδειγμα Αρχείου Εισόδου - Εξόδου:

toponyms.in	toponyms.out
7 Jora de Sus Orhei Jora de Mijloc Joreni Jora de Jos Japca Orheiul Vechi	24

Περιορισμοί:

• \(2 \leq N \leq 1.000.000\). Το μήκος κάθε τοπωνυμίου δε θα υπερβαίνει τους \(20.000\) χαρακτήρες. Το συνολικό μέγεθος του αρχείου εισόδου δε θα υπερβαίνει τα \(10\) MB.
• Όριο χρόνου εκτέλεσης: \(2\) sec.
• Όριο μνήμης: \(64\) MB.