segunda-feira, 19 de maio de 2014

[Programação em C] - Longest Common Subsequence (LCS)

Olá pessoal, nesse post iremos tratar da LCS (Longest Common Subsequence).

Exemplo: LCS de "ABCDGH" e "AEDFHR" é "ADH" cujo tamanho é 3. Nesse post iremos apresentar um modo bem simples para saber o tamanho da LCS entre duas strings. Lembrando que o modo que iremos apresentar é lento (complexidade 2^n no pior caso).

Para resolver esse problema de forma mais rápida é preciso utilizar programação dinâmica, pois o problema tem propriedade de subestrutura ótima.

Para você tentar resolver o problema, você terá que construir uma tabela, o vídeo a seguir é excelente caso você queira implementar o algoritmo (saber o tamanho da LCS e qual é a LCS).



Nenhum comentário: