In der Kodierungstheorie werden Wortsätze, von denen keines ein Präfix ist, häufig mit Non-Commit-Codes verwendet. Das Wort α wird als Präfix für das Wort β bezeichnet, wenn α aus β abgeleitet wird, indem am Ende Null oder mehr Zeichen entfernt werden. Zum Beispiel sind die Wörter a, ab und aba Präfixe des Wortes aba. Zum Beispiel ist der Wortsatz aba, aa und bac kein Commit-Code, während der Satz abac, aba, ba nicht vorhanden ist, da das Wort aba das Präfix des Wortes abac ist.
Professor Decifro arbeitet im Labor, um nutzlose Informationen zu untersuchen und seine neue Erfindung mit nahezu fehlerfreien Codes zu untersuchen. Ein Satz von Wörtern wird als nahezu fehlerfreier k -Level-Code bezeichnet, wenn das größte gemeinsame Präfix von zwei beliebigen Wörtern aus dem Satz die Länge von k nicht überschreitet. Zum Beispiel ist der Satz abac, abc, ba ein nahezu fehlerfreier Code der Ebene 2, während der Satz abac, abab, ba nicht vorhanden ist, da das größte gemeinsame Präfix der Wörter abac und abab die Länge 3 hat.
Eine weitere Aufgabe, die Professor Decifro seinen Laboranten gestellt hat, ist Folgendes: Für einen bestimmten Satz von Wörtern und die Zahl k müssen Sie den maximalen Satz aus den angegebenen Wörtern auswählen, der ein nahezu fehlerfreier Code auf k -Ebene ist. Sie wurden als Junior-Laborant angewiesen, ein entsprechendes Programm zu schreiben.
Geben Sie eine Zahl aus
m - die maximale Anzahl von Wörtern, die aus einem bestimmten Satz ausgewählt werden können, so dass sie einen nahezu fehlerfreien Code auf der Ebene von
k bilden.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
6 2
aba
bacaba
abacaba
baca
abac
caba
|
3 |