Space Complexity of Linear Time Approximate String Matching.
Borivoj MelicharPublished in: Stringology (1996)
Keyphrases
- space complexity
- approximate string matching
- suffix array
- worst case
- space requirements
- string matching
- genomic databases
- data structure
- edit distance
- suffix tree
- arc consistency
- space efficient
- n gram
- data compression
- pattern matching
- upper bound
- worst case time complexity
- databases
- constraint satisfaction
- np complete
- text classification