En la teoría de la codificación, los códigos sin prefijo a menudo se usan como conjuntos de palabras, ninguna de las cuales es un prefijo. Se dice que la palabra α precede a la palabra β si α se obtiene de β eliminando cero o más caracteres al final. Por ejemplo, las palabras a, ab y aba son prefijos de la palabra aba. Por ejemplo, el conjunto de palabras aba, aa y bac es un código sin prefijo, mientras que el conjunto de abac , aba< /code>, ba no está presente porque la palabra aba es un prefijo de la palabra abac.
El Profesor Decipher trabaja en el Laboratorio de Investigación de Información Inútil y estudia su nuevo invento de códigos casi prefijos. Un conjunto de palabras se denomina código casi sin prefijos de nivel k si el mayor prefijo común de dos palabras cualquiera del conjunto no supera la longitud de k. Por ejemplo, el conjunto abac, abc, ba es un código de nivel 2 casi sin prefijo, y el conjunto abac , abab, ba no existen porque el prefijo común más largo de abac y abab es 3.
La siguiente tarea que el profesor Decifro planteó a sus ayudantes de laboratorio es la siguiente: dado un conjunto de palabras y un número k, se requiere elegir entre los dados palabras el conjunto máximo, que es un código de nivel casi libre de prefijos k. A usted, como asistente de laboratorio junior, se le asignó la tarea de escribir el programa correspondiente.