A linear space algorithm for the heaviest common subsequence problem

Abstract

Let σ be an alphabet. For each letter in σ a positive weight is assigned to it. The weight of a string S over σ is defined as the sum of the weights of the letters in S. Let X and Y be two strings over an alphabet σ. The heaviest common subsequence problem for two strings X and Y is to find a sequence Z such that Z is the heaviest, i.e., having the largest weight, common subsequence for X and Y. In this note a linear space algorithm for the heaviest common subsequence problem for two strings is proposed.