Abstract
We show space-economical algorithms for finding maximal unique matches (MUM’s) between two strings which are important in large scale genome sequence alignment problems. Our algorithms require only O(n) bits (O(n/ log n) words) where n is the total length of the strings. We propose three algorithms for different inputs: When the input is only the strings, their compressed suffix array, or their compressed suffix tree. Their time complexities are O(n logn), O(n logϵn) and O(n) respectively, where e is any constant between 0 and 1. We also show an algorithm to construct the compressed suffix tree from the compressed suffix array using O(n logϵn) time and O(n) bits space.