On the Exact Complexity of String Matching: Lower Bounds.

Zvi Galil Raffaele Giancarlo

Published in: SIAM J. Comput. (1991)

Keyphrases

string matching
lower bound
exact and approximate
pattern matching
worst case
upper bound
approximate string matching
edit distance
objective function
suffix array
regular expressions
database
suffix tree
clone detection
aho corasick
knn
data structure
optimal solution