A vida tal
como a conhecemos depende do ADN (ácido desoxirribonucleico), um
composto orgânico cujas moléculas contêm as instruções genéticas que
controlam todo o funcionamento dos seres vivos. De um ponto de vista
químico, o ADN pode ser pensado como um polímero de unidades simples
denominadas nucleotídeos. Cada uma destas unidades simples é
distinguida pela sua base azotada: Adenina (A), Guanina
(G), Citosina (C) e Timina (T)).
Nos organismos vivos o ADN aparece na forma de uma dupla hélice, com duas cadeias de ADN interligadas entre si. Cada tipo de base numa cadeia liga-se apenas com um outro tipo de base complementar na outra cadeia. Desse modo, sabendo quais as bases azotadas de uma das cadeias, podemos automaticamente saber a constituição da outra cadeia. Com tudo isto, podemos pensar no ADN como uma longa palavra que usa como alfabeto apenas quatro letras: A, G, C e T. Por exemplo, estas são três cadeias (ou sequências) possíveis de ADN:
Sequência 1: AATCGTAGCTTTCGAA Sequência 2: ATTTAGCTTAGGCGTTAA Sequência 3: TTGTCAGCGTAAAA
Uma tarefa muito importante é conseguir comparar entre si várias cadeias de ADN, procurando descobrir semelhanças ou diferenças que justifiquem depois o funcionamento dos respectivos organismos. Por exemplo, como distinguir ao nível do ADN uma pessoa saudável de uma pessoa com uma determinada doença que possa ter origem genética?
Estás a trabalhar para um centro de genética molecular que está a precisar da tua ajuda para resolver um problema relacionado com informação genética. Eles têm N cadeias de ADN e querem descobrir qual a maior subcadeia que aparece pelo menos em K das cadeias originais. Uma subcadeia é uma subsequência de bases consecutivas da cadeia original (ex: as subcadeias de ATC são A, T, C, AT, TC e ATC). Considerando como exemplo as três cadeias dadas em cima, se estivéssemos à procura da maior subcadeia que aparece em pelo menos duas das cadeias originais, o melhor que conseguiriamos seria uma subcadeia de tamanho 6:
Sequência 1: AATCGTAGCTTTCGAA Sequência 2: ATTTAGCTTAGGCGTTAA
Se fosse necessário estar presente nas três cadeias originais, a maior passava a ter somente tamanho 3:
Sequência 1: AATCGTAGCTTTCGAA Sequência 2: ATTTAGCTTAGGCGTTAA Sequência 3: TTGTCAGCGTAAAA
Podes ajudar os biólogos nesta sua tarefa?
Dado um conjunto de N cadeias de ADN e o número K de sequências que queremos cobrir, a tua tarefa é descobrir qual o tamanho da maior subcadeia que aparece em pelo menos K dessas sequências.
Na primeira linha do input vêm dois números N e K, separados por um espaço, indicando respectivamente o número de cadeias de ADN a considerar e o número mínimo de cadeias originais onde a subcadeia procurada deve aparecer. Seguem-se exactamente N linhas, cada uma contendo uma cadeia de ADN de tamanho Tami, constituída unicamente por caracteres 'A', 'G', 'C' ou 'T'. Estas cadeias podem vir por qualquer ordem.
O output deve ter exactamente uma linha, contendo um único inteiro indicando o tamanho da maior subcadeia presente em pelo menos K das cadeias originais. Podem existir várias subcadeias máximas tocando em diferentes subconjuntos das cadeias originais, mas tal facto não altera o que terás de reportar, que é apenas o tamanho dessas subcadeias máximas.
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
| 1 ≤ N ≤ 200 | Número de cadeias ADN | |
| 1 ≤ K ≤ N | Número de cadeias onde a subcadeia máxima deve aparecer | |
| 1 ≤ Tami ≤ 100 | Tamanho de cada cadeia de ADN |
Para um conjunto de casos de teste valendo 50% dos pontos, o número de cadeias de ADN será inferior a 10, e o seu tamanho será inferior a 50.
3 2 AATCGTAGCTTTCGAA ATTTAGCTTAGGCGTTAA TTGTCAGCGTAAAA
6
3 3 AATCGTAGCTTTCGAA ATTTAGCTTAGGCGTTAA TTGTCAGCGTAAAA
3