Existe um algoritmo de programação dinâmica chamado LCS para manipulação de strings, porém não estou consiguindo entender como ele funciona. Alguma sugestão?
Nesse exercício vamos estudar o algoritmo de maior subsequência comum, ou em inglês, LCS - Logest Commom Subsequence.
Basicamente problemas de PD (programação dinâmica) como é o caso são definidos a partir de uma recorrência definida a partir dos chamados estados da PD, que nesse caso são as posições de cada uma das sequências. Vamos entender a recorrência para esse caso.
Assumamos que estamos na posição $i$ da sequência $A$ e na posição $j$ da sequência $B$. Se uma das posições for 0 (não estiver começado a sequência), isto é, se $i=0$ ou $j=0$, ou ainda, escrevendo de outra forma, se $i*j=0$, temos que a resposta é vazio. Se esse não for o caso e os dois elementos forem iguais ($a_i=b_j$), incrementamos a sequência procurada:
Compartilhar