Nella teoria dei codici, i codici senza prefisso sono spesso usati come insiemi di parole, nessuno dei quali è un prefisso. Si dice che la parola α prefissi la parola β se α è ottenuto da β cancellando zero o più caratteri alla fine. Ad esempio, le parole a, ab e aba sono prefissi della parola aba. Ad esempio, l'insieme di parole aba, aa e bac è un codice senza prefisso, mentre l'insieme di abac , aba, ba non è presente perché la parola aba è un prefisso della parola abac.
Il Professor Decipher lavora nel Laboratorio di ricerca sulle informazioni inutili e studia la sua nuova invenzione dei codici quasi prefissi. Un insieme di parole è chiamato codice quasi privo di prefisso di livello k se il massimo prefisso comune di due parole qualsiasi dell'insieme non supera k in lunghezza. Ad esempio, l'insieme abac, abc, ba è un codice di livello 2 quasi senza prefisso e l'insieme abac , abab, ba non esistono perché il prefisso comune più lungo di abac e abab è 3.
Il compito successivo che il Professor Decifro ha assegnato ai suoi assistenti di laboratorio è il seguente: dato un insieme di parole e un numero k, è necessario scegliere tra i dati parole l'insieme massimo, che è quasi privo di prefisso codice di livello k. Tu, come assistente di laboratorio junior, sei stato incaricato di scrivere il programma corrispondente.
Produci un singolo numero
m - il numero massimo di parole che possono essere selezionate dall'insieme dato in modo che formino un codice di livello
k quasi senza prefisso.
Esempi
| # |
Input |
Uscita |
| 1 |
6 2
aba
bacaba
abacaba
bacca
abac
caba
|
3 |