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(vertical bar T vertical bar(2)) time and space, achieving the answering time O(vertical bar P vertical bar + w), where U-r denotes the number of matched positions and w <= U-r. For the case of large-sized alphabets, our preprocessing can still be implemented with O(vertical bar T vertical bar(2)) time and space, while the answering time is slightly increased to O(vertical bar P vertical bar + w + log vertical bar T vertical bar). Compared to Wang's preprocessing algorithm with O(vertical bar T vertical bar(3)) time, our new indexing algorithm is a significant improvement. (C) 2011 Elsevier Inc. All rights reserved.
algorithm real-scale preprocessing string matching