International Journal of Computer Science Issues

More than a traditional journal...

In this paper, an improved algorithm that solves the Approximate String Matching (ASM) problem based on the Longest Common Subsequence (LCS) is presented. The LCS is defined as the longest common subsequence of characters that appears left-to-right between two given strings or substrings, a text called T, and a pattern called p. The improved algorithm solves the problem in less time and uses less space than the conventional LCS algorithm. It does this via a new technique based on the use of a one-dimensional array to order the matching characters between T and p, whereas the original LCS algorithm uses a two-dimensional matrix to order the matching characters, which requires more time and space.