Um estudo avançado do problema da Maior Subsequência Comum

Abstract

O problema da Maior Subsequência Comum é um problema clássico da Ciência da Computação que consiste em encontrar a mais longa subsequência de caracteres comuns a duas strings. A solução genérica é obtida pelo uso de uma matriz que combina estes caracteres dois a dois, com alto custo de tempo e uso de memória. Este trabalho busca soluções para o cálculo mais eficiente do comprimento da Maior Subsequência Comum. Para isso, propõe dois novos algoritmos denominados limpeza de matriz e diagonal. Para confirmar os resultados destes novos algoritmos são apresentadas e avaliadas as implementações de diversos trabalhos bem estudados na literatura que são comparados nas mesmas condições de ambiente. Adicionalmente, as soluções são submetidas ao repositório do Sphere online Judge (SPOJ) para confirmar os resultados pelo confrontamento com diferentes soluções de programadores de todo o mundo.

The problem of Longest Common subsequence (LCS) is a classic problem of computer science which is to find the longest subsequence of characters common to two strings. The general solution is obtained by use of a matrix that combines these two by two characters, with a high time cost and memory usage. This work seeks solutions for more efficient calculation of the length of the LCS. To this end, proposes two new algorithms called matrix cleaning and diagonal. To confirm the results of these new algorithms are presented and evaluated the implementation of several works well studied in the literature and compared in the same environmental conditions. In addition, these solutions are submitted to Sphere online Judge (SPOJ) repository to confirm the results by confrontation with different programmer solutions worldwide.