Searching BWT against Pattern Matching Machine to Find Multiple String Matches
Yangjun Chen, Yujia Wu · 2017
In this paper, we discuss an indexing method for solving the multiple string pattern matching problem, by which we are given a set of short strings R = {r1, ..., rl} and required to locate all substrings of a target string s such that each of them matches an rj in R. The main idea is to construct a pattern matching machine A and transform the reverse of s to a BWT-array as an index, denoted as BWT(s̅), and search A against it. During the process, the failure function of A is used to decrease the subranges of BWT(s̅) to be searched at each step. In addition, we change a single-character checking against BWT(s̅) to a multiple-character checking, by which multiple searches of BWT(s̅) are reduced to a single scanning. In this way, high efficiency can be achieved. Extensive experiments have been conducted, which shows that our method works better than almost all the existing methods for this problem.