An all-substrings common subsequence algorithm Original Research Article

Given two strings A and B of lengths image and image, image, respectively, the all-substrings longest common subsequence (ALCS) problem obtains, for every substring image of B, the length of the longest string that is a subsequence of both A and image. The ALCS problem has many applications, such as finding approximate tandem repeats in strings, solving the circular alignment of two strings and finding the alignment of one string with several others that have a common substring. We present an algorithm to prepare the basic data structure for ALCS queries that takes image time and image space. After this preparation, it is possible to build a matrix of size image that allows any LCS length to be retrieved in constant time. Some trade-offs between the space required and the querying time are discussed. To our knowledge, this is the first algorithm in the literature for the ALCS problem.