sábado, 26 de setembro de 2015

Programação dinâmica - Tamanho da maior subsequência comum (longest common subsequence)

Olá pessoal, nesse post iremos falar sobre o problema de encontrar o tamanho da maior subsequência comum entre duas strings (subsequência mais longa presente em ambas as strings). Esse problema é o LCS (longest common subsequence).

Essa maior subsequência comum não é necessariamente contígua, veja o exemplo:

string 1: ABCAD
string 2: BCD
Maior subsequência comum: BCD - tamanho 3

Para resolver esse problema de forma rápida temos que utilizar programação dinâmica cujo custo para uma string de tamanho "n" e outra de tamanho "m" será de theta(n*m).

Seja o tamanho de uma string "n" e o tamanho da outra string "m", precisamos construir uma matriz da ordem "n" por "m" onde a primeira linha e primeira coluna devem ser preenchidas com o valor 0.

As próximas células da matriz devem ser preenchidas da seguinte forma:

c[i, j] = c[i - 1, j - 1] + 1 se x[i] = y[j]
c[i, j] = max(c[i, j - 1], c[i - 1, j]) caso contrário

"x" e "j" são as strings. A variável "i" é a variável que percorre a string "x" e a variável "j" é a que percorre a string "y".

Veja a solução em C++:


Quaisquer dúvidas deixem nos comentários, até a próxima!




3 comentários:

Leonardo Costa disse...

Interessante.

Mas eu tenho outro desafio.

dado uma string contendo apenas pontos e hifens "." "-"

eg.: ----..---..---.-.-
a maior substring que se repete é ---..---.

consegue elaborar uma solução?

Anônimo disse...

Olá, blz?

Vc pretende futuramente explicar nos videos sobre C++11/14 usando lambdas e etc...?

Marcos Castro disse...

Pode ser, obrigado pela dica :)