A Fast and Exact Single Pattern Matching Algorithm

String matching problem is a fundamental problem in computer science. It is the key problem of many important scopes such as network security, information retrieval and filtration, computational biology, etc. And the design of exact single pattern string matching algorithm with high performance is the basis of all string matching problems. In this paper, the authors improve one of the fastest exact single pattern matching algorithms known on English text, which is SBNDM2. The simplest form of the BNDM core loop is obtained, in which there are only 5 instructions per character read by amending the relationship between position in the pattern and bit in the bitmask. And a cross-border protection method is added to the algorithm in order to reduce the cost of cross-border inspection. Two algorithms named S2BNDM and S2BNDM′ are presented. The experimental results indicate that both S2BNDM and S2BNDM′ are faster than SBNDM2 in any case. It can be considered that S2BNDM is the fastest algorithm on English text (2

Keywords:
• string matching, 
• exact single pattern, 
• design of algorithm, 
• bit parallelism, 
• text searching