Search

Bit Parallel String Matching algorithms are the most efficient and latest class of String Matching Algorithms. These algorithms use the intrinsic property of computer known as Bit Parallelism for performing bit operations in parallel with-in single computer word. BNDM, TNDM, BNDMq are the popular single pattern bit parallel string matching algorithms whereas Shift-OR and Shift-OR with Q-grams algorithms are popular in multiple pattern string matching. All these algorithms are restricted by the limitation of pattern size. These all algorithms are not working on patterns whose sizes are longer than computer word. In this paper, we proposed the generic method named WSR (Word Size Removal) for bit parallel string matching. With the inclusion of WSR these bit parallel string matching algorithms can work on longer than computer word size patterns. This paper presented WSR method and all modified algorithms.

Pattern Matching with Swaps (PMS for short) is a variation of the classical pattern matching problem where a match is allowed to include disjoint local swaps. In 2009, Cantone and Faro devised a new dynamic programming algorithm for PMS, named Cross-Sampling, that runs in O(nm) time and uses O(m) space. More important, Cross-Sampling admits a linear-time implementation based on bit parallelism when the pattern's size is comparable to the word size of the machine. In this paper, we present improved dynamic programming formulations of the approach of Cantone and Faro for PMS which result in simpler algorithms that are much easier to be comprehended and implemented.

We present a new algorithm for exact multiple string matching. Our algorithm is based on filtration combining BNDM and q-grams. We have tested it with experiments and compared it with other algorithms, e.g. DFA, AC_BM and MWM. The preprocessing phase of our algorithms is fast, the memory usage is fairly small, and our algorithm is considerably faster for huge sets of several thousand patterns. The benefits are due to the bit parallelism of BNDM and the improved filtering efficiency by q-grams.