Maior substring em comum

Bacharelao em Ciência da Computação - UFU
Disciplina - Análise de Algoritmos - 2014/2
Profa. Sandra de Amo
TRABALHO 2: Maior substring em comum : GRUPO 9
Considere o seguinte problema: Dados dois strings x = x1 x2 ...xm e y = y1 y2 ...yn deseja-se
encontrar o maior substring em comum entre os dois strings, isto é, o maior k para o qual existem
indices i e j tais que xi xi+1 ...xi+k−1 = yj yj+1 ...yj+k−1 . Por exemplo, se x = SANDRA e y =
ANDRE, o maior substring em comum é ANDR, de comprimento 4.
Pede-se:
1. Projetar um algoritmo de programação dinâmica de complexidade O(m.n), que resolve
o problema do maior substring enunciado acima. Enuncie claramente os subproblemas
dando seus inputs e outputs e diga como são ordenados. Apresentar o algoritmo em
pseudo-código !!
2. Prove que a complexidade do algoritmo projetado em (a) é O(m.n).
3. Implemente o algoritmo cujo pseudo-código foi dado em (a). Só parta para a implementação do algoritmo DEPOIS de tê-lo projetado cuidadosamente (em (a)) e ter analisado sua complexidade (em (b)).
4. Execute seu algoritmo no seguinte input:
x = ANTICONSTITUCIONALISSIMAMENTE e y = POSCONSTITUCIONAL
1