On the Exact Complexity of String Matching (Extended Abstract)

Livio Colussi Zvi Galil Raffaele Giancarlo

Published in: FOCS (1990)

Keyphrases

extended abstract
string matching
exact and approximate
pattern matching
edit distance

pattern matching algorithm
suffix tree
aho corasick
data sets
approximate string matching

regular expressions
approximate matching
computer vision
suffix array

structured data
query processing
clone detection
neural network