TY - CONF
T1 - Efficient approximate and dynamic matching of patterns using a labeling paradigm
T2 - Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on
Y1 - 1996
A1 - Sahinalp,S. C
A1 - Vishkin, Uzi
KW - algorithm;replaced
KW - algorithmics;substrings;suffix
KW - algorithms;pattern
KW - approximate
KW - characters;dynamic
KW - characters;labeling
KW - characters;string
KW - complexity;indexing;parallel
KW - construction;computational
KW - data
KW - dictionary
KW - dynamic
KW - indexing;efficient
KW - matching;deleted
KW - matching;dynamic
KW - matching;efficient
KW - matching;inserted
KW - matching;string
KW - matching;tree
KW - paradigm;optimal
KW - Parallel
KW - pattern
KW - PROCESSING
KW - string
KW - structures;
KW - text
KW - tree
AB - A key approach in string processing algorithmics has been the labeling paradigm 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 by the authors in 1994 the labeling paradigm was considered not to be competitive with other approaches. They show that this general method is also useful for several central problems in the area of string processing: approximate string matching, dynamic dictionary matching, and dynamic text indexing. The approximate string matching problem deals with finding all substrings of a text which match a pattern ldquo;approximately rdquo;, 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 preprocessed. In the dynamic text indexing problem, updates to the text in the form of insertions and deletions of substrings are permitted. The dictionary matching problem deals with finding all occurrences of each pattern set of a set of patterns in a text, after the pattern set is preprocessed. In the dynamic dictionary matching problem, insertions and deletions of patterns to the pattern set are permitted
JA - Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on
M3 - 10.1109/SFCS.1996.548491
ER -