The Research For Fast Exact String Matching Algorithm

String matching algorithm is the important research topic in computer application, information retrieval and computational biology and so on. It has a broad application in the daily life and scientific research. With the development of computer technology and network technology, new applications continue to increase the requirements of real-time of the matching. In this paper, on the bases of studying the research and status of the exact string matching problem and its various methods, I deeply and systematicly study the BM algorithm and WM algorithm, which are widely used in exact string matching for single-mode and multi-pattern string matching, and propose the corresponding improved algorithms, whose superiorities are experimentally verified. The main concepts of this paper are as follows:1. analyse the research situation at home and abroad of string-matching algorithm, discuss the three kinds of search methods under exact string matching in detail, study and implement some typical algorithms under single-pattern string matching and multi-pattern string matching, including Shift-And and Shift-Or algorithm, Horspool algorithm, BNDM and BOM algorithm, AC algorithm, WM algorithm, SBOM algorithm.?2. In the traditional BM algorithm, when no matching occurs, the maximum distance of matching window moved is much smaller and the maximum safe distance of matching window moved is also not big enough. Therefore, to the speed of string matching, there is still room for improvement. In view of this situation, this paper presents a new improved BM algorithm, which can increase the average moving distance. Firstly, in the pre-processing stage , the algorithm calculates the moving distance using any two characters as the character block ,and sets the maximum moving distance as the length of string plusing one; then, in the searching stage,it increases the large distances moving probability by comparing the two consecutive character blocks. Experimental results show that the algorithm can improve the speed significantly comparing to the original algorithms.?3. When not matching,the safe moving distance of the traditional WM algorithm is clear small,and the moving distance is more conservative after the pattern string matching,what's more,the probability of single matching and the whole pattern string not matching is much larger.To solve these problems, this paper presents a new improved WM algorithm, which firstly improve the SHIFT table, significantly improving the safe moving distance,secondly,improve searching algorithm,making the probability of single matching and the whole pattern string not matching down by increasing the comparing character block,and making the moving distance after pattern string matching not been one. Experiments show that the algorithm is better than the original algorithm with faster matching speed.?...