An all-substrings common subsequence algorithm

Given two strings A and B   of lengths nana and nbnb, na⩽nbna⩽nb, respectively, the all-substrings longest common subsequence (ALCS) problem obtains, for every substring B′B′ of B, the length of the longest string that is a subsequence of both A   and B′B′. 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 O(nanb)O(nanb) time and O(na+nb)O(na+nb) space. After this preparation, it is possible to build a matrix of size O(nb2) 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.