AN IMPROVED STRING MATCHING ALGORITHM BASED ON SUFFIX ARRAY

摘要：

The paper presents an improved algorithm based on suffix array for string matching. In paper, by utilizing a generalized algorithm, called DC3. that allows a space-efficient implementation and. moreover, supports the choice of a space-time tradeoff, we get the suffix array in linear time. Meanwhile, in order to reduce matching time, the new algorithm improves the search conditions in the process of accurate string matching and filters the suffix strings which do not meet the conditions to reduce the times of the character comparison. Comparing the improved algorithm with the original one. the experiment results show that the new algorithm saves query time and increases matching efficiency on the condition of increasing space complexity properly.

关键词： String matching Suffix array Rank array Difference cover

作者: HUIMIN JIA SONGFENG LIT

作者单位: College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430 College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430

会议类型: 国际会议

会议名称: 3rd International Conference on Mechanical and Electrical Technology(ICMET2011) (2011第三届机械与电气技术国际会议)

会议地点: 大连

会议语种:英文

页码: 579-583

在线出版日期: 2011-08-26（万方平台首次上网日期，不代表论文的发表时间）