  The problem of aligning two strings A,B in order to determine their
similarity is fundamental in the field of pattern matching. An important
concept in this domain is the "all scores matrix" that encodes the local
alignment comparison of two strings. Namely, let K denote the all scores matrix
containing the alignment score of every substring of B with A, and let J denote
the all scores matrix containing the alignment score of every suffix of B with
every prefix of A.
  In this paper we consider the problem of maintaining an all scores matrix
where the scoring function is the LCS score, while supporting single character
prepend and append operations to A and N. Our algorithms exploit the sparsity
parameters L=LCS(A,B) and Delta = |B|-L. For the matrix K we propose an
algorithm that supports incremental operations to both ends of A in O(Delta)
time. Whilst for the matrix J we propose an algorithm that supports a single
type of incremental operation, either a prepend operation to A or an append
operation to B, in O(L) time. This structure can also be extended to support
both operations simultaneously in O(L log log L) time.
