uCoder | 1260 | Nível: 3 | Tempo Limite: 4
Vacina
Adaptado por Erich Rodrigues
Competição: Interfatecs 2016 1ª Fase
Os laboratórios do mundo inteiro andam em polvorosa a busca de uma vacina que consiga combater as três doenças transmitidas pelo mosquito Aedes aegypt: chikungunya, dengue e zika vírus. Uma das pesquisas concentra-se em encontrar uma subsequência de DNA contida nos três vírus, que possam ser estudados e consequentemente achar um padrão para a criação de uma vacina.
Francisco Bento, é formado em biomedicina e trabalha em um desses laboratórios, porém em conversa com seu filho Bernardo que estuda TI na FATEC ele descobriu que tais padrões são uma sequência de letras que podem ou não se repetir. Por exemplo a subsequência “AAGG” é um segmento da palavra AAAAGGCC, enquanto a subsequência TTTG não é encontrado na sequência GGAAGGCC. Assim para mapear o DNA dos três vírus, tais subsequências devem ser encontradas em três palavras diferentes, de acordo com um comprimento T . Por exemplo, se Francisco decidir que T = 3, então ele considera “AGG” como uma subsequência comum aceitável de AAGGBDDD, AGGGGGGG e GATAGGCC. Neste caso AGG foi encontrando somente uma vez nos três filamentos de DNA. Se Francisco decidir que o tamanho da subsequência T = 2 onde para dengue com filamento de DNA AAGG, chikungunya AAGT e zica AAGC temos que a subsequência AA se repete nos 3 filamentos, assim como AG, neste caso teremos duas subsequências se repetindo nos 3 filamentos.
Com base nesta ideia, você poderia ajudar Bernardo a criar um algoritmo que encontre a quantidade de subsequências que se repetem nos três vírus?
Entrada
A entrada consiste de vários casos de testes. A primeira linha de cada caso de teste contém uma cadeia de caracteres indicando um filamento de DNA do chikungunya com o tamanho X (4 ≤ X ≤ 15). A segunda linha contém outro filamento de DNA da dengue com tamanho D (4 ≤ D ≤ 15) e a terceira linha contém outro filamento de DNA para o zica com tamanho Z (4 ≤ Z ≤ 15). A última linha contém o tamanho da subsequência a ser encontrada T (2 ≤ T ≤ 15). As entradas não possuem espaços em branco.
Saída
Para cada caso de teste na entrada, seu programa deve imprimir uma única linha, contendo a quantidade de sequencias que se repetem dentro do segmento.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
GGGTTTCCC |
0 |
|
AAGG |
3 |