On the Complexity of the Extended String-to-String Correction Problem
Robert A. WagnerPublished in: STOC (1975)
Keyphrases
- string matching
- pattern matching
- edit distance
- data structure
- regular expressions
- space complexity
- worst case
- context free grammars
- artificial intelligence
- data sets
- approximate string matching
- evolutionary algorithm
- machine learning
- data mining
- probabilistic model
- computational cost
- relational databases
- database systems
- suffix tree
- database