Efficient Approximate and Dynamic Matching of Patterns Using a Labeling Paradigm (Extended Abstract)
Süleyman Cenk Şahinalp, Uzi Vishkin, Suleyman Cenk S · 1996
A key approach in string processing algorithmics has been the labeling paradigm [KMR72], which is based on assigning labels to some of the substrings of a given string. If these labels are chosen consistently, they can enable fast comparisons of substrings. Until the first optimal parallel algorithm for suffix tree construction was given in [SV94], the labeling paradigm was considered not to be competitive with other approaches. In this paper we show that, this general method is also useful for several central problems in the area of string processing: ffl Approximate String Matching, ffl Dynamic Dictionary Matching, ffl Dynamic Text Indexing. The approximate string matching problem deals with finding all substrings of a text which match a pattern "approximately", i.e., with at most m differences. The differences can be in the form of inserted, deleted, or replaced characters. The text indexing problem deals with finding all occurrences of a pattern in a text, after the text is prep...