Two Improved Fast Single Pattern Matching Algorithms of QS
Zhou Zhi-pin · Journal of Sanming University · 2013
Pattern matching algorithms has been widely used in various fields. Aiming at how to reduce the number of attempts as well as improve the efficiency of the algorithm, two pattern matching algorithms are presented to improve the algorithm of quick search. The first algorithm matches the text window by checking whether the last character occurs in the pattern string, and then shifts the pattern string depending on the situation. The second algorithm constructs two bad character shift tables of BM and QS algorithms', then look up these two tables to determine the shift distance each time, making the pattern string reach the maximum shift distance. This greatly reduces the number of attempts and increases the shift distance. The experimental results show that UCD and MSD algorithms' matching speed is significantly faster than QS and other algorithms'.