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(|T|~2) time and space, achieving the answering time O(|P| +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(|T|~2) time and space, while the answering time is slightly increased to O(|P| + w + log|T|). Compared to Wang's preprocessing algorithm with O(|T|~3) time, our new indexing algorithm is a significant improvement.