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 O(2|T|) time and space, achieving the answering time O(|P|+w), where Ur denotes the number of matched positions and w⩽Ur. For the case of large-sized alphabets, our preprocessing can still be implemented with O(2|T|) time and space, while the answering time is slightly increased to O(|P|+w+log|T|). Compared to Wangʼs preprocessing algorithm with O(3|T|) time, our new indexing algorithm is a significant improvement.