A new efficient indexing algorithm for one-dimensional real scaled patterns

摘要

Given a pattern string P and a text string T, the one-dimensional real-scale pattern matching problem is to ask for all matched positions in T at which P occurs for some real scales ⩾1. The real-scale indexing problem, which is derived from the real-scale matching problem, aims to preprocess T, so that all positions of scaled P in T can be answered efficiently. In this paper, we propose an improved algorithm for the real-scale indexing problem. For constant-sized alphabets, our preprocessing takes time and space, achieving the answering time , where denotes the number of matched positions and . For the case of large-sized alphabets, our preprocessing can still be implemented with time and space, while the answering time is slightly increased to . Compared to Wangʼs preprocessing algorithm with time, our new indexing algorithm is a significant improvement.