Problema C



DNA



A biologia, estes últimos anos, sofreu revoluções notáveis graças à aplicação dos computadores e da programação aos problemas de análise de dados de origem biológica, em particular na área da genética quando aplicada por exemplo à análise do genoma/DNA (humano).

Vamos aqui descobrir um problema clássico desta área de resolução algorítmica, igualmente clássica. Assim, no wikipédia podemos ler:

Uma sequência de DNA ou sequência genética é uma série de letras representando a estrutura primária de uma molécula ou cadeia de DNA, real ou hipotética, com a capacidade de carregar informação. As letras possíveis são A, C, G e T, representando os quatro nucleotídeos (subunidades) de uma cadeia de DNA — as bases adenina, citosina, guanina, timina.

Uma sucessão de quaisquer nucleotídeos maior que quatro está apta a ser considerada uma sequência. Com respeito à sua função biológica, a qual pode depender do contexto, uma sequência pode ou não "fazer sentido".

Destacar sub-sequências de DNA funcionais (que “parecem” fazer sentido) da sequência do DNA humano (enorme, que tem um comprimento total de aproximadamente dois metros!) é uma tarefa simplesmente titanesca que só pode ser realizada com a ajuda de computadores.

Um critério interessante para destacar a potencial relevância de um segmento de DNA é o da semelhança ou ainda repetição de padrão. Ou seja, se duas sequências de DNA distintas tiverem partes em que se assemelham, e quanto maiores estas partes forem, maior potencial de relevância estas (partes) têm.

O desafio aqui é destacar estas semelhanças.

Problem

Escreva um programa que lê duas sequências ADN e que devolva a (primeira dentro da primeira sequência, se há mais do que uma) maior sub-sequência de ADN comum.

Input

A entrada deste exercício consiste em quatro linhas.

Na primeira linha aparece o tamanho n1 da primeira sequência de DNA por considerar.

Na segunda linha é dado a sequência de letras (ou ’A’ ou ’C’ ou ’G’ ou, finalmente, ’T’) de comprimento n1 que compõe a primeira sequência de DNA por considerar.

Na terceira linha aparece o tamanho n2 da segunda sequência de DNA por considerar.

Na quarta linha é dado a sequência de letras (ou ’A’ ou ’C’ ou ’G’ ou, finalmente, ’T’) de comprimento n2 que compõe a segunda sequência de DNA por considerar.

Output

A saída está organizada numa linha. Esta contém a sequência de letras (ou ’A’ ou ’C’ ou ’G’ ou, finalmente, ’T’) que representa a (primeira da primeira sequência, se há mais do que uma) maior parte commum.

Constraints

Sample Input

61
AACGTTGAGATTGAAGTCCGTGCATGGCCCGTGAGAGTCACTTTCGGATTAGCTGTGAATG
45
AACATTGCGTAATGGCCGTAGGCCCGTGAGAGTCACTTTCTTGAT

Sample Output

GGCCCGTGAGAGTCACTTTC

This document was translated from LATEX by HEVEA.