The Research For High Performance Exact Single Pattern String Matching Algorithm

String matching problem is a fundamental problem in computer science. It is used in most of the application related to string treatment. Meanwhile, it is the key problem of information retrieval, network security, and computational biology. The exact single pattern string matching problem is the basis of all of string matching problem. With the highlight of network security, with the high speed development of networking and computation biology, and with the phenomenon of "Information explosion" becoming serious, the string matching applications require higher performance string matching algorithm. Therefore, It has become a new challenge to design the string matching algorithms (the exaxt single pattern string matching algorithms especially) with higher performance.This dissertation mainly describe the research of high performance exact single pattern string matching algorithm. It has been considered that there are two algorithms are the fastest above English, Tuned BM and SBNDM2, through analyzing the existing exact single pattern string matching algorithms. In this paper, these two fastest algorithms were improved respectively, and DQM algorithm and S2BNDM algorithm were put forward.On the whole, the main results of this dissertation are as following:1. The existing high performance exact single pattern string matching algorithms were analyzed. The research direction for string matching was given. The result showed that there are two algorithms are the fastest above English, Tuned BM and SBNDM2.2. A suffix matching type exact single pattern string matching algorithm~DQM, based on tuned BM, was presented. It use two judgement characters jump alternately by BM badchar role to reduce the increase of the probability of the judgement-character matching. It has an improved cross-broader protection method to reduce the cost of checking cross-broader. And It use bit operation and action combination method to improve the action after the judgement-character matching so as to reduce the branch operations. The experiment results show that DQM is faster than Tuned BM.3. A substring matching type high performance exact single pattern stirng matching algorithm--S2BNDM, based on SBNDM2, was presented. It reach the simplest form of the core loop of BNDM (5 instructions per character read) by amending the definition of the bitmask. And It add the cross-border protection method which is used in DQM to our algorithm. The experimental results indicated that S2BNDM could be considered as the fastest algorithm above English text for the pattern shorter than the length of machine word and above DNA sequence for the pattern shorter than 8.