On the Common Substring Alignment Problem

The Common Substring Alignment Problem is defined as follows: Given a set of one or more strings S₁, S₂ … S_c and a target string T, Y is a common substring of all strings S_i, that is, S_i = B_iYF_i. The goal is to compute the similarity of all strings S_i with T, without computing the part of Y again and again. Using the classical dynamic programming tables, each appearance of Y in a source string would require the computation of all the values in a dynamic programming table of size O(nℓ) where ℓ is the size of Y. Here we describe an algorithm which is composed of an encoding stage and an alignment stage. During the first stage, a data structure is constructed which encodes the comparison of Y with T. Then, during the alignment stage, for each comparison of a source S_i with T, the pre-compiled data structure is used to speed up the part of Y. We show how to reduce the O(nℓ) alignment work, for each appearance of the common substring Y in a source string, to O(n)-at the cost of O(nℓ) encoding work, which is executed only once.