Matching statistics: efficient computation and a new practical algorithm for the Multiple Common Substring Problem
We present new algorithms for computing matching statistics with suffix arrays. We show how the Multiple Common Substring Problem can be solved efficiently in practice with a new approach using matching statistics. This problem consists of finding the common substrings of a set of strings. For the computation of matching statistics we compare seven different methods based on suffix trees and suffix arrays. Most of the suffix array algorithms have an inferior asymptotic worst case running time but a very low memory overhead and small constants in the running time complexity. Our experiments show a good performance in practice. Copyright (c) 2005 John Wiley & Sons, Ltd.
matching statistics common substring problem suffix array suffix tree algorithms and data structures pattern matching