An Efficient Multiple Patterns String Matching Algorithm
Jiamin Xu · Jisuanji gongcheng · 2014
Combined with the advantages of BM-Horspool(BMH) algorithm and Quick-Search(QS) algorithm,an effective algorithm to perform multiple patterns matching in a string is proposed on the concept of Fan-Su(FS) algorithm.To reduce the number of comparisons,and improve the efficiency of matching,the proposed algorithm skips as many characters as possible and avoids useless state transitions,by making full use of the successful and failing information during the matching.Experimental results show that the proposed algorithm can achieve more excellent performance than the ACBM algorithm and FS algorithm.The time it takes for the proposed algorithm to search a string is only 10%~35%of the AC algorithm,50%~60%of the ACBM algorithm,70%of the FS algorithm,and 65%of the FSQB algorithm.