Analysis and Implementation of Long Pattern Matching Approaches
Ferenc Galk, Magyar Tud · 2014
Suffix arrays and suffix trees are well-known for their capability of efficiently solving string processing problems including exact string matching, which has many uses in a variety of fields like computational molecular biology and search engines. In this paper we present a novel way to use hash tables for exact string matching as well as our detailed comparison of the different approaches, throughout carefully selected test suites ranging from proteins to English texts. Our experimental results show that in many areas our hash table based version outperforms even the best known suffix array and suffix tree based solutions, thus indicate that this approach is not only of theoretical interest.