Dictionary-Matching on Unbounded Alphabets: Uniform Length Dictionaries

✍ Scribed by D. Breslauer

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 861 KB
• Volume: 18
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1995.1011

✦ Synopsis

In the string-matching problem one is interested in all occurrences of a short pattern string in a longer text string. Dictionary-matching is a generalization of this problem where one is looking simultaneously for all occurrences of several patterns in a single text. This paper presents an efficient on-line dictionary-matching algorithm for the case where the patterns have uniform length and the input alphabet is unbounded. A tight lower bound establishes that our approach is optimal if the only access the algorithm has to the input strings is by pairwise symbol comparisons. In an immediate application, the new dictionary-matching algorithm can be used in a previously known higher dimensional array-matching algorithm, improving the performance of this algorithm on unbounded alphabets. The resulting algorithm is currently the fastest known algorithm for (k)-dimensional array-matching on unbounded alphabets, for (k \geq 3). O 1995 Academic Press, Inc.