A Complete Suffix Array-based String Match Search Algorithm of Sliding Windows
String match has been widely used in such diverse areas as data compression, search engine, information retrieval. Due to its simplicity and high-efficient space, suffix array is used to improve the efficiency of string match. However, the existing suffix arraybased algorithms will rebuild suffix array after window slides every time. According to the properties of sliding window, the concept of completed suffix array and a new sliding window search algorithm for string matching using the orderly construction of suffix arrays are proposed. Thus, it is unnecessary that suffix array is rebuilt every time. Both theoretical analysis and experimental results show the improved efficiency of the proposed algorithm.
string match suffix array sliding window completed suffix array
Lu Wang Kun Huang Jian Zhang Jin Yao
China ship development and design center 268 Zhang Zhidong Road, Wuchang District, Wuhan 430064, China
国际会议
杭州
英文
788-791
2012-10-28（万方平台首次上网日期，不代表论文的发表时间）